Hamilton cycles in random lifts of graphs (Q5898131): Difference between revisions

The notion of a random \(n\)-lift of a graph was introduced in [\textit{A. Amit} and \textit{N. Linial}, Combinatorica 22, No. 1, 1--18 (2002; Zbl 0996.05105)]. Given a base graph \(K\), we form a random graph \(G\) with vertex set \(V(K)\times \{1,2,\ldots n\}\) and with edges consisting of a random perfect matching between the sets \(\{u\}\times \{1,2,\ldots n\}\) and \(\{v\}\times \{1,2,\ldots n\}\) exactly when \(u\) and \(v\) are adjacent in \(K\). Here each of the \(n!\) such perfect matchings is equally likely to be chosen, and the matchings between different fibres (i.e. sets \(\{u\}\times \{1,2,\ldots n\}\)) are independent of each other. In the paper just mentioned, the authors showed that if \(K\) is connected with \(\delta(K)\geq 3\), then \textbf{whp} \(G\) has vertex connectivity at least \(\delta(K)\). (Here \textbf{whp} means with probability tending to 1 as \(n\rightarrow\infty\).) Subsequent papers in this vein include [\textit{A. Amit} and \textit{N. Linial}, Comb. Probab. Comput. 15, 317--332 (2006; Zbl 1095.05034), \textit{A. Amit, N. Linial} and \textit{J. Matoušek}, Random Struct. Algorithms 20, 1--22 (2002; Zbl 0993.05071) and \textit{N. Linial} and \textit{E. Rozenman}, Combinatorica 25, No. 4, 407--424 (2005; Zbl 1091.05063)]. A more recent paper is [\textit{Y. Drier} and \textit{N. Linial}, Random Struct. Algorithms 29, 208-225 (2005; Zbl 1226.05235)]. The paper under review has two main theorems, both concerning when random lifts are Hamiltonian (have a Hamilton cycle). Firstly, there exists a constant \(h_{1}\) such that if \(h\geq h_{1}\) then a random lift of \(K_{h}\) is Hamiltonian \textbf{whp}. Secondly, there is a constant \(h_{2}\) such that if \(h\geq h_{2}\) then a random lift of \(K_{h,h}\) is Hamiltonian \textbf{whp}. The method of proof does not give much insight into the values of \(h_{1}\) and \(h_{2}\) and it would be of some interest to understand these two numbers better. The proof of the first result is roughly as follows. We fix a certain graph \(F\), which is a subgraph of our random lift \(G\). \(F\) has minimum degree at least 12 and contains a fixed longest path of \(G\). We say that a set \(H\) of edges is acceptable if it contains \(F\) and \(H\) has \(\beta {h\choose 2}n\) edges, for an unspecified small positive constant \(\beta\), and we also use \(H\) for the graph induced by these edges. We then show that \textbf{whp} a not-too-large subset of an acceptable \(H\) has good expanding properties (in a precise sense): this then implies, with some work, that \(H\) is \textbf{whp} connected. It now suffices to show that the proportion of the lifts which are connected and have this good expansion property which are not Hamiltonian tends to zero: this step uses the so-called \` coloring argument\'\, of the fourth author and T. I. Fenner. (Warning: the notation \({\mathcal H}(G)\) for the collection of acceptable subgraphs of \(G\), used in the statement of Lemma 2 etc. is not formally defined until later in the paper.) For the proof of the second result, we wish to use a \` Pósa-type argument\', but a problem is that in a bipartite graph a longest path of even length of course cannot be completed, by adding one edge, to a cycle. The authors thus follow an idea of Bollobás and Kohayakawa. By techniques similar to those in the first proof, they prove that small enough sets have decent expansion properties. They also (easily) obtain a 2-factor in \(G\). The aim is now to perturb this into a Hamilton cycle, and the authors give a process which will achieve this. As in the first proof, a 0-1 matrix with rows indexed by random lifts and columns by acceptable subgraphs of the lift plays a role in the argument.