Speaker
Rosalind Cameron
(Memorial University)
Description
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)
