Universality for transversal Hamilton cycles in random graphs

Micha Christoph, Anders Martinsson, Aleksa Milojević · 2025

Read Universality for transversal Hamilton cycles in random graphs by Micha Christoph, Anders Martinsson, Aleksa Milojević (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-05385.txt.

Introduction

Micha Christoph, Anders Martinsson, and Aleksa Milojević prove a universality result for ring tours that mix many graphs at once. Imagine several networks drawn on the same towns. A tour must visit every town once and return, with each leg borrowed from a network chosen by a fixed rule. When can every rule be satisfied?

An earlier theorem answered this for dense networks with high minimum degree. The new result handles sparse random networks instead. Each network is drawn with the same modest edge chance, just above a logarithmic floor. With high probability, the family is then universal for tours. The proof couples a classic randomization trick with a colorful tree-growing method. It extends a Dirac-style guarantee into the sparse world where real networks live.

Catalog record

CREATORMicha Christoph, Anders Martinsson, Aleksa Milojević
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-05385

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Universality for transversal Hamilton cycles in random graphs Micha Christoph, Anders Martinsson, Aleksa Milojević Abstract A tuple ( G 1 , … , G n ) (G_{1},\dots,G_{n}) of graphs on the same vertex set of size n n is said to be Hamilton-universal if for every map χ : [ n ] → [ n ] \chi:[n]\to[n] there exists a Hamilton cycle whose i i -th edge comes from G χ ⁡ ( i ) G_{\chi(i)} . Bowtell, Morris, Pehova and Staden proved an analog of Dirac’s theorem in this setting, namely that if δ ⁡ ( G i ) ≥ ( 1 / 2 + o ⁡ ( 1 ) ) ​ n \delta(G_{i})\geq(1/2+o(1))n then ( G 1 , … , G n ) (G_{1},\dots,G_{n}) is Hamilton-universal. Combining McDiarmid’s coupling and a colorful version of the Friedman-Pippenger tree embedding technique, we establish a similar result in the setting of sparse random graphs, showing that there exists C C such that if the G i G_{i} are independent random graphs sampled from G ⁡ ( n , p ) G(n,p) , where p ≥ C ​ log ⁡ n / n p\geq C\log n/n , then ( G 1 , … , G n ) (G_{1},\dots,G_{n}) is Hamilton-universal with high probability. 1 Introduction One of the most fundamental questions in graph theory is that of determining whether a given graph contains a Hamilton cycle, i.e. a cycle which contains all vertices of the graph. There is no simple algorithm to check whether a graph contains such a cycle – the problem of finding a Hamilton cycle in a given graph is famously NP-complete. Therefore, researchers focused on finding easy-to-check conditions which ensure that a graph contains such a cycle, and perhaps even allow for finding the cycle in polynomial time. The most famous condition of the kind is Dirac’s condition [ 6 ] , dating back to 1952, which states that every n -vertex graph of minimum degree at least n/2 must contain a Hamilton cycle. Although Dirac’s condition is undoubtedly elegant, and tight in the sense that the degree requirement n/2 cannot be lowered, it is quite restrictive – for example, it can only be satisfied by dense graphs which have quadratically many edges. It is, therefore, natural to ask what kind of conditions guarantee the existence of Hamilton cycles in sparser graphs. A common family of sparse graphs to study are the random graphs. The study of Hamilton cycles in random graphs is almost as old as the study of random graphs – in their original paper from 1960 [ 8 ] , Erdős and Rényi asked for the number of edges at which one expects to start seeing a Hamilton path in a random graph G(n,m) . This question was answered by Pósa [ 17 ] , who showed that one can expect Hamilton cycles in random graphs with \Omega(n\log n) edges, by introducing a very useful and elegant technique now known as the Pósa rotation. His argument was later tightened by Komlós and Szemerédi [ 13 ] , and Bollobás [ 4 ] and Ajtai, Komlós and Szemerédi [ 2 ] , to ultimately attain very good understanding of Hamilton cycles in random graphs. Namely, Bollobás, as well as Ajtai, Komlós and Szemerédi, showed that if we order the edges of K_{n} randomly and add them one by one to our graph, the time at which the graph becomes Hamiltonian with high probability coincides with the first time at which no vertex has degree less than 2, which is clearly a necessary condition for the graph to be Hamiltonian. In recent years, the study of Hamilton cycles and other spanning structures in graphs has taken an interesting turn, by considering the colorful variants of classical questions from extremal graph theory. In particular, the setup we will be studying was introduced by Joos and Kim in [ 12 ] while answering a question of Aharoni [ 1 ] , and it goes as follows. Given a collection of m graphs (G_{1},\dots,G_{m}) on the same vertex set V , which we think of as colors of the edges (where an edge may receive an arbitrary number of colors), and a graph H with vertices in V , we say that (G_{1},\dots,G_{m}) contains a rainbow (or transversal) copy of H if there exists an injective function \psi:E(H)\to[m] such that the edge e is contained in the graph G_{\psi(e)} for all e\in E(H) . In other words, the graph H can be constructed by picking at most one edge from each of the graphs G_{i} . Joos and Kim showed that if each of the graphs G_{i} is an n -vertex graph with minimum degree n/2 and if m\geq n , then there exists a transversal Hamilton cycle in the collection (G_{1},\dots,G_{m}) . This result inspired a large body of work on the subject, for example studying the existence of transversal cliques [ 1 ] , transversal F -factors [ 16 ] and transversal Hamilton cycles in random graphs [ 3 ] . We recommend the survey of Sun, Wang and Wei [ 18 ] to the interested reader who would like to learn more about the transversal subgraphs of graph collections. In this paper, we will consider the question of universality for Hamilton cycles in collections of random graphs. The notion of universality was introduced by Bowtell, Morris, Pehova and Staden in [ 5 ] . We say that a collection of graphs (G_{1},\dots,G_{n}) on the same vertex set of size n is Hamilton-universal if for each map \chi:[n]\to[n] , which we call the color-pattern , there exists a Hamilton cycle whose i -th edge lies in G_{\chi(i)} . The authors of [ 5 ] showed that every collection (G_{1},\dots,G_{n}) of n graphs on the same vertex set of size n satisfying \delta(G_{i})\geq(1/2+o(1))n is Hamilton-universal. Note that the difference from the result of Joos and Kim is that the edges of the Hamilton cycle must now come from a prescribed member of the collection (G_{1},\dots,G_{n}) , rather than an arbitrary one. The aim of this paper is to extend the result of Bowtell, Morris, Pehova and Staden to the setting of random graphs, answering a question of Pehova from the 30 th British Combinatorial Conference. Theorem 1.1 . There exists C such that for p\geq C\log n/n the following holds with high probability. Let (G_{1},\ldots,G_{n}) be a tuple of independent random graphs on the same vertex set sampled from G(n,p) . Then, (G_{1},\ldots,G_{n}) is Hamilton-universal. Note that the above result is tight up to the constant C , since by considering the color-pattern \chi(i)=1 for all i , the graph G_{1} is required to contain a Hamilton cycle for (G_{1},\dots,G_{n}) to be Hamilton-universal. While showing the existence of a Hamilton cycle with any specific color-pattern is sufficient for Hamilton-universality in the deterministic setting, dealing with the looming union bound over all color-patterns is the key obstacle to overcome towards Theorem 1.1 . 1.1 Proof sketch We will now go through a short outline of the proof of our result. The tool underlying our proof, called McDiarmid’s coupling, is a method which allows us to go from Hamilton cycles in

Read the complete text