Extended commonality of paths and cycles via Schur convexity

DOI10.1016/J.JCTB.2023.12.001arXiv2210.00977WikidataQ129749758 ScholiaQ129749758MaRDI QIDQ6196155FDOQ6196155

Authors: Jang Soo Kim, Joonkyung Lee 

Publication date: 14 March 2024

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: 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}ightarrow[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}ightarrowmathbbR$ 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.

Full work available at URL: https://arxiv.org/abs/2210.00977

Recommendations

• Off-diagonal commonality of graphs via entropy
• Multiplicities of subgraphs
• Non-three-colourable common graphs exist
• Non-bipartite \(k\)-common graphs
• On tripartite common graphs

zbMATH Keywords

Schur convexityRamsey multiplicitygraph homomorphism inequalities

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Large networks and graph limits
• Inequalities: theory of majorization and its applications
• Non-three-colourable common graphs exist
• Title not available (Why is that?)
• Quasi-random graphs
• Decision Trees and Influences of Variables Over Product Probability Spaces
• Compactness results in extremal graph theory
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• Title not available (Why is that?)
• On Sets of Acquaintances and Strangers at any Party
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• Two inequalities in nonnegative symmetric matrices
• A correlation inequality for bipartite graphs
• An Inequality Arising in Genetical Theory
• Graph norms and Sidorenko's conjecture
• Multiplicities of subgraphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• On the Ramsey multiplicities of graphs—problems and recent results
• There exist graphs with super‐exponential Ramsey multiplicity constant
• Cycles in graphs and functional inequalities
• Finite reflection groups and graph norms
• Inequalities for functionals generated by bipartite graphs
• The positive-definiteness of the complete symmetric functions of even order
• Convex graphon parameters and graph norms
• Sidorenko's conjecture for blow-ups
• Title not available (Why is that?)
• On the sign patterns of entrywise positivity preservers in fixed dimension
• Common and Sidorenko equations in abelian groups
• Positive graphs
• On tripartite common graphs
• A new proof of the Erdős-Simonovits conjecture on walks
• On graph norms for complex‐valued functions
• A Property on Monochromatic Copies of Graphs Containing a Triangle

Cited In (1)

• Off-diagonal commonality of graphs via entropy

This page was built for publication: Extended commonality of paths and cycles via Schur convexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196155)