What is the independence number of this graph which is a generalization of a Kneser graph? 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.
 A: 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.
A: 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...
