Twofold triple systems that disprove Tutte's conjecture

Not scheduled
UP FHS (Koper)



Titov trg 5,Koper


Rosalind Cameron (Memorial University)


The *$2$-block intersection graph* ($2$-BIG) of a twofold triple system is the graph whose vertex set is the blocks of the $TTS$ and two vertices are joined by an edge if they intersect in exactly two elements. A Hamilton cycle in a $2$-BIG is equivalent to a cyclic Gray code, so an interesting problem is to classify which $TTS$s have Hamiltonian $2$-BIGs. The $2$-BIGs are themselves interesting graphs: each component is cubic and $3$-connected, and a $2$-BIG is bipartite exactly when the $TTS$ is decomposable to two Steiner triple systems. Any connected, bipartite $2$-BIG with no Hamilton cycle is a counter-example to Tutte's conjecture. Our main result is that for all $v\equiv 1\, \rm{ or }\, 3\, ({\rm mod }\, 6)$ such that $v>N$ , there exists a simple, decomposable $TTS(v)$ whose $2$-BIG is connected but not Hamiltonian. $N$ is currently about $700$ but this has the potential to be improved. Our result is achieved by embedding a simple, decomposable $TTS(u)$ with connected $2$-BIG inside another simple, decomposable $TTS(v)$ with connected $2$-BIG where ${v>2u+c}$. We also use a Tutte-like fragment to construct a decomposable, simple $TTS(331)$ whose $2$-BIG is connected but not Hamiltonian.

Primary authors

David Pike (Memorial University) Rosalind Cameron (Memorial University)

Presentation Materials

There are no materials yet.