
Probability and Statistics Basic Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
October 2nd, 2015, 07:00 AM  #1 
Newbie Joined: Oct 2015 From: Poland Posts: 1 Thanks: 0  Find max size of clique in permutation graph
Hello, I have following problem. I have following graph: 1 3 1 5 1 4 2 4 2 3 2 5 3 4 which looks like below I want to calculate permutation for this graph. My result is: (4 3 5 1 2) But it looks that is wrong answer. Size of the largest clique in permutation graph is equal to the longest decreasing subsequence of permutation. The longest decreasing subsequence of my permutation is 2, when the largest clique has size equals to 3. Could you please help me with this issue? I would appreciaty any help that you can provide. Best regards Antek 
October 2nd, 2015, 05:32 PM  #2 
Senior Member Joined: Oct 2013 From: New York, USA Posts: 673 Thanks: 88 
I'm not sure I understand the question. If by permutations you mean how many line segments met each point, just count the frequency of each number in the original list, making the answer (3 3 3 3 2).


Tags 
clique, find, graph, max, permutation, size 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Find size of projected image using distances  Kamster  Geometry  0  April 22nd, 2014 08:42 PM 
Set size is relative  Same topology of negative size sets  BenFRayfield  Applied Math  4  December 21st, 2013 10:58 PM 
Find the Mafia!: an iOS game on the maximum clique problem  experiware  Applied Math  1  June 17th, 2013 12:52 PM 
find an inverse of a permutation cycle  rayman  Abstract Algebra  5  January 29th, 2012 01:26 AM 
Number of ways to make a graph from nsize vertex set  Singularity  Applied Math  1  April 15th, 2011 06:42 AM 