Extended commonality of paths and cycles via Schur convexity (Q6196155)

A graph \(H\) is called 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 (measurable symmetric function) \(W : [0, 1]^{2} \rightarrow [0, 1]\), where \(t_{H}(.)\) denotes the homomorphism density of the graph \(H\). The main result of this paper is to prove a new homomorphism density inequality for paths and cycles, which extends their commonality. 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. It can also be interpreted as a `convexity-type' homomorphism inequality, as the proof uses convexity of certain functions and deduction of commonality from it also uses convexity. This answers a question of \textit{A. F. Sidorenko} [Math. Notes 46, No. 5, 877--882 (1989; Zbl 0717.05041); translation from Mat. Zametki 46, No. 5, 72--79 (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 \textit{N. Behague} et al. [``Common Pairs of Graphs'', Preprint, arXiv:2208.02045 [math.CO] (2022)] in a strong form, who asked if the inequality holds for graphons \(W\) and odd cycles \(H\). The authors' proof uses Schur's convexity of complete homogeneous symmetric functions, which may be of independent interest. Two open questions conclude the paper.