标题： 随机摄动图中的颜色偏差哈密顿回路 显示英文标题

标题： Colour-biased Hamilton cycles in randomly perturbed graphs

摘要： 给定一个图$G$和$r$- 边着色$\chi$在$E(G)$上，若哈密顿回路$H\subset G$包含$t$条相同颜色的边，则称$H$包含$n/r+t$条相同颜色的边在$\chi$中。 弗雷西、海德、拉达和特雷格洛温证明了每个具有$r$-着色的图$G$，在$n$个顶点上且有$\delta(G)\geq(r+1)n/2r+t$条边，包含一个具有$\Omega(t)$色彩偏差的哈密顿回路$H$，推广了巴拉格、巴萨、京和普卢哈尔的结果。 2022年，Gishboliner、Krivelevich 和 Michaeli 证明了随机图$G(n,m)$在$m\geq(1/2+\varepsilon)n\log n$的情况下，在任意$r$-着色下通常会存在一个$\Omega(n)$阶的色彩偏差哈密顿圈。本文研究了随机扰动图中的色彩偏差哈密顿圈。 我们证明了对于每个$\alpha>0$，向一个拥有$\delta(G_\alpha)\geq \alpha n$条边的图$G_\alpha$添加$m=O(n)$条随机边通常会确保在任何$r$-着色下存在一个具有$\Omega(n)$着色偏差的哈密顿圈$G_\alpha\cup G(n,m)$。 相反，对于某些 $G_{\alpha}$，将随机边的数量减少到 $m=o(n)$ 可能会消除某种着色下所有 $G(n,m)\cup G$ 的颜色偏置哈密顿回路。 相比之下，在临界端点 $\alpha=(r+1)/2r$ 处，增加 $m$ 条随机边通常会导致一种具有 $\Omega(m)$ 颜色偏置的哈密顿回路，对于任何 $1\ll m\leq n$ 都成立。 显示英文摘要

摘要： Given a graph $G$ and an $r$-edge-colouring $\chi$ on $E(G)$, a Hamilton cycle $H\subset G$ is said to have $t$ colour-bias if $H$ contains $n/r+t$ edges of the same colour in $\chi$. Freschi, Hyde, Lada and Treglown showed every $r$-coloured graph $G$ on $n$ vertices with $\delta(G)\geq(r+1)n/2r+t$ contains a Hamilton cycle $H$ with $\Omega(t)$ colour-bias, generalizing a result of Balogh, Csaba, Jing and Pluh\'{a}r. In 2022, Gishboliner, Krivelevich and Michaeli proved that the random graph $G(n,m)$ with $m\geq(1/2+\varepsilon)n\log n$ typically admits an $\Omega(n)$ colour biased Hamilton cycle in any $r$-colouring. In this paper, we investigate colour-biased Hamilton cycles in randomly perturbed graphs. We show that for every $\alpha>0$, adding $m=O(n)$ random edges to a graph $G_\alpha$ with $\delta(G_\alpha)\geq \alpha n$ typically ensures a Hamilton cycle with $\Omega(n)$ colour bias in any $r$-colouring of $G_\alpha\cup G(n,m)$. Conversely, for certain $G_{\alpha}$, reducing the number of random edges to $m=o(n)$ may eliminate all colour biased Hamilton cycles of $G(n,m)\cup G$ in a certain colouring. In contrast, at the critical endpoint $\alpha=(r+1)/2r$, adding $m$ random edges typically results in a Hamilton cycle with $\Omega(m)$ colour-bias for any $1\ll m\leq n$.