Skip to main content
MathOverflow

Return to Answer

Improved example
Source Link
Ilya Bogdanov
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

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

Here is an independent set of 188 vertices, if I'm not mistaken.

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.

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

Source Link
Ilya Bogdanov
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

Here is an independent set of 188 vertices, if I'm not mistaken.

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.