My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum

LinkBack Thread Tools Display Modes
October 2nd, 2015, 07:00 AM   #1
Joined: Oct 2015
From: Poland

Posts: 1
Thanks: 0

Find max size of clique in permutation graph


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 is offline  
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).
EvanJ is offline  

  My Math Forum > High School Math Forum > Probability and Statistics

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 n-size vertex set Singularity Applied Math 1 April 15th, 2011 06:42 AM

Copyright © 2019 My Math Forum. All rights reserved.