论文标题
通过Schur凸的路径和周期的扩展通用性
Extended commonality of paths and cycles via Schur convexity
论文作者
论文摘要
图$ h $是\ emph {commun}，如果在2 edge the The Guleth Graph $ k_n $中的单色副本数量为$ h $的数量是由随机着色或等效地将$ t_h（w）+t_h（w）+t_h（1-w）（1-W）（1-W）（1-W）\ geq 2^{1-e（h）$ nograph nakers y逐渐最小化。 $ w：[0,1]^2 \ rightarrow [0,1] $，其中$ t_h（。）$表示图$ h $的同构密度。由于Mulholland和Smith（1959），Goodman（1959）和Sidorenko（1989），路径和周期是极端图理论中最早的基石之一。 我们证明了图形同态不平等，该图形扩展了路径和周期的共同点。 Namely, $t_H(W)+t_H(1-W)\geq t_{K_2}(W)^{e(H)} +t_{K_2}(1-W)^{e(H)}$ whenever $H$ is a path or a cycle and $W:[0,1]^2\rightarrow\mathbb{R}$ is a bounded symmetric measurable function. 这回答了1989年Sidorenko的一个问题，他证明了证明奇数循环的共同点的长度途径的结果略有弱。此外，它还以强烈的形式解决了最近的贝格，莫里森和诺埃尔的猜想，他们询问不平等是否适合Graphons $ W $和ODD CYCLES $ H $。我们的证明使用了完全均匀对称函数的Schur凸度，这可能具有独立的兴趣。
A graph $H$ is \emph{common} if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is asymptotically minimised by the random colouring, or equivalently, $t_H(W)+t_H(1-W)\geq 2^{1-e(H)}$ holds for every graphon $W:[0,1]^2\rightarrow [0,1]$, where $t_H(.)$ denotes the homomorphism density of the graph $H$. Paths and cycles being common is one of the earliest cornerstones in extremal graph theory, due to Mulholland and Smith (1959), Goodman (1959), and Sidorenko (1989). We prove a graph homomorphism inequality that extends the commonality of paths and cycles. Namely, $t_H(W)+t_H(1-W)\geq t_{K_2}(W)^{e(H)} +t_{K_2}(1-W)^{e(H)}$ whenever $H$ is a path or a cycle and $W:[0,1]^2\rightarrow\mathbb{R}$ is a bounded symmetric measurable function. This answers a question of Sidorenko from 1989, who proved a slightly weaker result for even-length paths to prove the commonality of odd cycles. Furthermore, it also settles a recent conjecture of Behague, Morrison, and Noel in a strong form, who asked if the inequality holds for graphons $W$ and odd cycles $H$. Our proof uses Schur convexity of complete homogeneous symmetric functions, which may be of independent interest.
