Let $\mathfrak{A}=\{1,2,\dots,8\}$ and construct a graph as follows. Let the vertices of the graph be the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ are distinct. Two vertices $(\{a,b,c\},\{d,e\})$ and $(\{f,g,h\},\{k,l\})$ are adjacent if $\{a,b,c\}=\{f,g,h\}$ and $\{a,b,c,d,e\} \cap \{f,g,h,k,l\}=\{a,b,c\}$ or if $\{d,e\}=\{k,l\}$ and $\{a,b,c,d,e\} \cap \{f,g,h,k,l\}=\{d,e\}$.

My question is what is the independence number of this graph?

Recall that the independence number of a graph is the maximum number of vertices with no edge between them.

  • $\begingroup$ Note that B and C have an edge iff their union has 7 or 8 elements. So an independent set of vertices can't have two sets with a union of more than 7 elements. You can now choose either a set of four vertices all sharing 4 elements, or all 6 vertices contained in a set of six elements. Gerhard "I Would Go With Six" Paseman, 2016.02.16. $\endgroup$ Feb 16, 2016 at 16:39
  • 3
    $\begingroup$ You need to clarify the question. See Aaron's answer and the comments after it. $\endgroup$ Feb 17, 2016 at 1:04
  • 2
    $\begingroup$ Maryam, are $B=(\lbrace1,2,3\rbrace,\lbrace4,5\rbrace)$ and $C=(\lbrace1,2,6\rbrace,\lbrace4,5\rbrace)$ adjacent? In the new version of the question they are adjacent ($B$ and $C$ are sets of size 2 whose intersection is $\lbrace4,5\rbrace$). Or do you mean us to consider the intersection of $\lbrace1,2,3,4,5\rbrace$ and $\lbrace1,2,6,4,5\rbrace$? $\endgroup$ Feb 17, 2016 at 14:02
  • $\begingroup$ @ Brendan, No they are not adjacent because of 3 in $B$ and 6 in $C$. I think if we consider this graph as a generalization of usual Kneser graph, the definition is much clear. $\endgroup$
    – Maryam
    Feb 17, 2016 at 14:43
  • 2
    $\begingroup$ In fact all adjacent vertices of $B$ are $(\{1,2,3\},\{67\}),(\{1,2,3\},\{68\}),(\{1,2,3\},\{7,8\}),(\{6,7,8\},\{4,5\}),$ $\endgroup$
    – Maryam
    Feb 17, 2016 at 14:53

2 Answers 2


So the graph has $\binom83 \binom52=560$ vertices and is regular of degree $4$? If so it might be clearer to say that the vertices are labelled by ordered pairs $(\{{a,b,c\}},\{{d,e\}})$. Then the vertices $({\{1,b,c\}},\{{d,8\}})$ give an independent set of size $60.$ Add the vertices $({\{b,c,8\}},\{{1,d\}})$ to get size $120$. I have no idea how good that is.

later I was going to comment that one could add the points $(\{{1,8,a\}},\{{b,c\}})$ and half the points $(\{{a,b,c\}},\{1,8\})$ to get $154.$ However Flo gets $180$ in a more elegant manner below. No independent set could have size $224$ as I'll show.

The graph is interesting. For convenience, color the edges so that a vertex $v=(\{{a,b,c\}},\{{d,e\}})$ is connected by a red edge to $w=(\{{f,g,h\}},\{{d,e\}})$ and by black edges to $(\{{a,b,c\}},\{{f,g\}}),(\{{a,b,c\}},\{{f,h\}})$ and $(\{{a,b,c\}},\{{g,h\}}).$ Ignoring the red edges divides the graph into $56$ connected graphs with $10$ vertices and regular of degree $3.$ These are quickly seen from the combinatorial description to be Peterson Graphs with indepence number $4.$ Hence the upper bound of $56 \cdot 4=224.$

Fixing the two element set gives $20$ points disjoint save for $10$ red edges. There are $11$ isomorphism classes of $10$ independent points (i.e. $10$ pairwise intersecting $3$-subsets of a $6$-set). The most symmetric has symmetry group the exceptional embedding of $A5$ in $S6.$ However an independent set of $224$ points would on average use $8$ out of each of those $10$ points so that is where I would look.

  • $\begingroup$ 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. $\endgroup$ Feb 16, 2016 at 19:23
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Feb 16, 2016 at 19:27
  • 4
    $\begingroup$ Although a literal reading matches Gerhard and Tony's interpretation, my money is on Aaron's interpretation being what the OP intended. $\endgroup$ Feb 17, 2016 at 1:03
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 18, 2016 at 18:11
  • 3
    $\begingroup$ 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$. $\endgroup$ Feb 18, 2016 at 18:15

Here is an independent set of 188 vertices, if I'm not mistaken. (At the end it is improved to 194...)

It seems more convenient to rename the vertices. Each vertex $(abc,de)$ gets a new name $[de,fgh]$ where $\{a,b,c,d,e,f,g,h\}=\{1,2,3,4,5,6,7,8\}$. Then two vertices $[de,fgh]$ and $[d'e',f'g'h']$ are connected if either $\{d,e\}=\{d',e'\}$ and $\{f,g,h\}\cap \{f',g',h'\}=\varnothing$, or $\{d,e\}\cap\{d',e'\}=\varnothing$ and $\{d,e,f,g,h\}=\{d',e',f',g',h'\}$. So, ten vertices with the same underlying set $\{d,e,f,g,h\}$ form a Petersen graph mentioned by Aaron Meyerowitz. We say that such 10-tuple of vertices is a group.

Now, take 46 of these groups such that their underlying sets $S$ contain 0, 1, or 2 elements from $\{6,7,8\}$. We choose from each such group four vertices; depending on $|S\cap\{6,7,8\}|$, these vertices have the following forms:

(0) $[1e,fgh]$ (so $\{e,f,g,h\}=\{2,3,4,5\}$);

(1) $[de,fgh]$, where $d\in\{6,7,8\}$ (so $\{e,f,g,h\}\subset\{1,\dots,5\}$);

(2) a bit more complicated: if the underlying set contains $\{6,7\}$, $\{7,8\}$, or $\{8,6\}$, then the vertices have respectively the forms $[6e,fgh]$, $[7e,fgh]$, or $[8e,fgh]$.

Now, it is clear that two chosen vertices with the same underlying set are not connected, since their pairs have a common element.

Assume that we have chosen two connected vertices whose underlying sets intersect by two elements. These may be either two vertices from (2), or a vertex from (2) and that from (1).

A vertex $[de,fgh]$ from (1) and a vertex $[d'e',f'g'h']$ from (2). Their underlying sets have two common elements from $\{1,2,3,4,5\}$, so their intersections with $\{6,7,8\}$ are disjoint. But each of the pairs $\{d,e\}$ and $\{d',e'\}$ contains an element from $\{6,7,8\}$, so these pairs are distinct.

Two vertices from (2): their underlying sets cannot contain the same pair of elements from $\{6,7,8\}$, otherwise these sets have at least three common elements. If, say, one set contains $\{6,7\}$ and the other contains $\{7,8\}$, then the first vertex has the form $[6e,fgh]$, while the second one cannot have such form.

[EDIT] It is more efficient to remove group (0) and to put instead 10 vertices of the form $[de,678]$ (no vertex $[d'e',f'g'h']$ from (1) and (2) has pair $\{d',e'\}\subset\{1,\dots,5\}$). This gives 194. Hope it's not optimal, otherwise I hardly imagine a proof of the optimality...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.