2024/03/19 by Bahmanian, Amin, Shan, Songling
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.12713
Motivated by generalizations of de Bruijn cycles to various combinatorial structures (Chung, Diaconis, and Graham), we study various Euler tours in set systems. Let G be a hypergraph whose corank and rank are c≥ 3 and k, respetively. The minimum t-degree of G is the fewest number of edges containing every t-subset of vertices. An Euler tour (family, respectively) in G is a (family of, respectively) closed walk(s) that (jointly, respectively) traverses each edge of G exactly once. An Euler tour is spanning if it traverses all the vertices of G. We show that G has an Euler family if its incidence graph is (1+\lceil k/c \rceil)-edge-connected. Provided that the number of vertices of G meets a reasonable lower bound, and either 2-degree is at least k or t-degree is at least one for t≥ 3, we show that G has a spanning Euler tour. To exhibit the usefulness of our results, we solve a number of open problems concerning ordering blocks of a design (these have applications in other fields such as erasure-correcting codes). Answering a question of Horan and Hurlbert, we show that a Steiner quadruple system of order n has a (spanning) Euler tour if and only if n≥ 8 and n≡ 2,4 \pmod 6, and we prove a similar result for all Steiner systems, as well as all designs except for 2-designs whose index λ is less than the largest block size. We nearly solve a conjecture of Dewar and Stevens on the existence of universal cycles in pairwise balanced designs. Motivated by R.L. Graham's question on the existence of Hamiltonian cycles in block-intersection graphs of Steiner triple systems, we establish the Hamiltonicity of the block-intersection graph of a large family of (not necessarily uniform) designs. All our results are constructive and of polynomial time complexity.