On the profile of multiplicities of complete subgraphs

DOI10.1137/19M1268859MaRDI QIDQ4959760zbMATH OpenFDO

Authors Anne Kenyon, Shimon Kogan, Uriel Feige

Publication date 7 April 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

combinatoricsRamsey multiplicityRamsey theory

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Ramsey theory (05D10)

Abstract: Let $G$ be a $2$-coloring of a complete graph on $n$ vertices, for sufficiently large $n$. We prove that $G$ contains at least $n^{(frac14-o(1))logn}$ monochromatic complete subgraphs of size $r$, where [ 0.3log n < r < 0.7log n. ] The previously known lower bound on the total number of monochromatic complete subgraphs, due to Sz'{e}kely was $n^{0.1576logn}$. We also prove that $G$ contains at least $n^{frac17logn}$ monochromatic complete subgraphs of size $frac12logn$. If furthermore one assumes that the largest monochromatic complete subgraph in $G$ is of size $(frac12+o(1))logn$ (it is a well known open question whether such graphs exist), then for every constant $0leclefrac12$ we determine (up to low order terms) the number of monochromatic complete subgraphs of size $clogn$. We do so by proving a lower bound that matches (up to low order terms) a previous upper bound of Sz'{e}kely. For example, the number of monochromatic complete subgraphs of size $frac12logn$ is $n^{frac18(4-logepmo(1))logn}simeq{n}^{0.32logn}$.

Recommendations

• On the Ramsey multiplicity of complete graphs
• Two-colorings with many monochromatic cliques in both colors
• Highly connected monochromatic subgraphs of two-colored complete graphs
• Note on highly connected monochromatic subgraphs in 2-colored complete graphs
• Lower bounds on the number of monochromatic matchings in \(K_{2s+t-1}\)

Cites work

• 2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• Multiplicities of subgraphs
• On Sets of Acquaintances and Strangers at any Party
• On the number of homogeneous subgraphs of a graph
• On the profile of multiplicities of complete subgraphs
• On the Ramsey multiplicities of graphs—problems and recent results
• On the Ramsey multiplicity of complete graphs
• Some remarks on the theory of graphs
• Spectral functions, special functions and the Selberg zeta function
• Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey

Cited in

(9)

• Graph products and monochromatic multiplicities
• Multiplicities of subgraphs
• scientific article; zbMATH DE number 4089601 (Why is no real title available?)
• A Remark on the Number of Complete and Empty Subgraphs
• On the Ramsey multiplicity of complete graphs
• scientific article; zbMATH DE number 749253 (Why is no real title available?)
• On the profile of multiplicities of complete subgraphs
• On the distribution of monochromatic complete subgraphs and arithmetic progressions
• On the number of monochromatic cliques in a graph

This page was built for publication: On the profile of multiplicities of complete subgraphs

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