On the Ramsey multiplicity of complete graphs

DOI10.1007/S00493-012-2465-XzbMATH Open1299.05245arXiv0711.4999OpenAlexW2019438351MaRDI QIDQ452823FDOQ452823

Authors: David Conlon 

Publication date: 17 September 2012

Published in: Combinatorica (Search for Journal in Brave)

Abstract: We show that, for $n$ large, there must exist at least [frac{n^t}{C^{(1+o(1))t^2}}] monochromatic $K_t$s in any two-colouring of the edges of $K_n$, where $Capprox2.18$ is an explicitly defined constant. The old lower bound, due to ErdH{o}s cite{E62}, and based upon the standard bounds for Ramsey's theorem, is [frac{n^t}{4^{(1+o(1))t^2}}.]

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

Recommendations

• On the profile of multiplicities of complete subgraphs
• scientific article; zbMATH DE number 3882480
• scientific article; zbMATH DE number 4106899
• A lower bound for the Ramsey multiplicity of \(K_4\)
• Ramsey numbers of several \(K_{t,s}\) and a large \(K_{m,n}\)

zbMATH Keywords

complete graphedge two-coloringmonochromatic complete graph

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• On Sets of Acquaintances and Strangers at any Party
• Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey
• On Erdős's conjecture on multiplicities of complete subgraphs: Lower upper bound for cliques of size 6
• Multiplicities of subgraphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• 2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs

Cited In (37)

• A lower bound for the Ramsey multiplicity of \(K_4\)
• Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems
• Ramsey's theorem and self-complementary graphs
• Explicit Ramsey graphs and orthonormal labelings
• Title not available (Why is that?)
• String graphs and incomparability graphs
• The shift graph and the Ramsey degree of \([\mathbb N]^\omega\)
• When is an Almost MonochromaticK₄Guaranteed?
• Title not available (Why is that?)
• A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs
• Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs
• Edges not in any monochromatic copy of a fixed graph
• Induced Turán numbers
• On the profile of multiplicities of complete subgraphs
• There exist graphs with super‐exponential Ramsey multiplicity constant
• Monochromatic triangles in three-coloured graphs
• On the combinatorial structure of Rauzy graphs
• Title not available (Why is that?)
• An improved lower bound for multicolor Ramsey numbers and a problem of Erdős
• Ramsey precompact expansions of homogeneous directed graphs
• On highly ramsey infinite graphs
• Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs
• On book-complete graph Ramsey numbers
• Short proofs of some extremal results. III
• On the number of monotone sequences
• On uncommon systems of equations
• A note on the inducibility of 4-vertex graphs
• Ramsey-type problem for an almost monochromatic \(K_4\)
• Remarks on the application of Ramsey numbers to bounding the sum of densities of a graph and its complement
• Threshold Ramsey multiplicity for paths and even cycles
• The number of additive triples in subsets of abelian groups
• Ramsey for complete graphs with a dropped edge or a triangle
• On Ramsey numbers for special complete distance graphs
• Extremal problems and results related to Gallai-colorings
• Title not available (Why is that?)
• On a conjecture of Erdős for multiplicities of cliques
• Linear configurations containing 4-term arithmetic progressions are uncommon

This page was built for publication: On the Ramsey multiplicity of complete graphs

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