标题： 随机图中横向哈密顿圈的普适性 显示英文标题

标题： Universality for transversal Hamilton cycles in random graphs

摘要： 一个定义在相同顶点集上的大小为$n$的图的元组$(G_1,\dots,G_n)$被称为 Hamilton-普适的，如果对于每个映射$\chi: [n]\to[n]$都存在一条 Hamilton 回路，且其第$i$条边来自$G_{\chi(i)}$。Bowtell、Morris、Pehova 和 Staden 在此背景下证明了 Dirac 定理的一个类似结果，即如果$\delta(G_i)\geq (1/2+o(1))n$，则$(G_1,\dots,G_n)$是 Hamilton-普适的。 结合麦克迪亚米德耦合方法以及弗里德曼-皮彭伯格树嵌入技术的彩色版本，我们在稀疏随机图的背景下得到了一个类似的结果，证明了存在$C$使得如果$G_i$是从$G(n,p)$中独立采样的随机图，其中$p\geq C\log n/n$，那么$(G_1,\dots,G_n)$高概率上是哈密顿通用的。 显示英文摘要

摘要： A tuple $(G_1,\dots,G_n)$ of graphs on the same vertex set of size $n$ is said to be Hamilton-universal if for every map $\chi: [n]\to[n]$ there exists a Hamilton cycle whose $i$-th edge comes from $G_{\chi(i)}$. Bowtell, Morris, Pehova and Staden proved an analog of Dirac's theorem in this setting, namely that if $\delta(G_i)\geq (1/2+o(1))n$ then $(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$ such that if the $G_i$ are independent random graphs sampled from $G(n,p)$, where $p\geq C\log n/n$, then $(G_1,\dots,G_n)$ is Hamilton-universal with high probability.