Timeline for What is the independence number of this graph which is a generalization of a Kneser graph?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 22, 2016 at 7:14 | comment | added | Aaron Meyerowitz | Maryam. I found a set with 204. If I can't improve it I'll put it up. If one could do 224 that would be the exact number. Otherwise I don't know. There are 60 points which use neither 1 nor 8 and another 120 (as I mentioned) that use both, but in differant parts. Together, 180. | |
| Feb 19, 2016 at 13:34 | comment | added | Maryam | Aaron, Is it possible to get the exact number not a bound? | |
| Feb 19, 2016 at 13:32 | comment | added | Maryam | Flo, how you get the number 180? I can not understand? | |
| Feb 18, 2016 at 22:03 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 1267 characters in body
|
| Feb 18, 2016 at 18:15 | comment | added | Flo Pfender | starting with your set of size 120, you can add all sets made from $\{2,3,...,7\}$, bringing your count up to $120+{6\choose 3}{3\choose 2}=180$. | |
| Feb 18, 2016 at 18:11 | comment | added | Flo Pfender | Since it is 4-regular and not $K_5$, it is 4-colorable, so it has an independent set of size at least 560/4=140. | |
| Feb 17, 2016 at 8:47 | comment | added | Christian Stump | And only that interpretation is computationally hard. The indepentence number for the simple interpretation is 6. | |
| Feb 17, 2016 at 1:03 | comment | added | Brendan McKay | Although a literal reading matches Gerhard and Tony's interpretation, my money is on Aaron's interpretation being what the OP intended. | |
| Feb 16, 2016 at 19:27 | comment | added | Tony Huynh | I thought the same thing as Gerhard. The description seems to be a complicated way of saying that the vertices are the 5-sets of an 8-set, and two 5-sets are adjacent if they intersect in exactly 2 or 3 elements. | |
| Feb 16, 2016 at 19:23 | comment | added | Gerhard Paseman | I think the vertex set is 5-sets of an 8-set. If not, union is not a good choice of notation for describing A, B, and C. Gerhard "Perhaps Original Poster Will Clarify" Paseman, 2016.02.16. | |
| Feb 16, 2016 at 19:09 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |