4
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\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$
    – Gerhard Paseman
    Commented Feb 16, 2016 at 16:39
  • 3
    $\begingroup$ You need to clarify the question. See Aaron's answer and the comments after it. $\endgroup$
    – Brendan McKay
    Commented 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$
    – Brendan McKay
    Commented 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
    Commented 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
    Commented Feb 17, 2016 at 14:53

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\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$
    – Gerhard Paseman
    Commented 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
    Commented 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$
    – Brendan McKay
    Commented 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$
    – Flo Pfender
    Commented 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$
    – Flo Pfender
    Commented Feb 18, 2016 at 18:15
0
$\begingroup$

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...

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .