Anti-Ramsey Multiplicities

MaRDI QIDQ5377035zbMATH OpenFDO

Authors

Publication date 23 May 2019

Full work available at URL https://arxiv.org/abs/1801.00474, http://ajc.maths.uq.edu.au/pdf/73/ajc_v73_p357.pdf

zbMATH Keywords

anti-Ramsey multiplicityRamsey multiplicity constant of a graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Abstract: The Ramsey multiplicity constant of a graph $H$ is the minimum proportion of copies of $H$ in the complete graph which are monochromatic under an edge-coloring of $K_n$ as $n$ goes to infinity. Graphs for which this minimum is asymptotically achieved by taking a random coloring are called {em common}, and common graphs have been studied extensively, leading to the Burr-Rosta conjecture and Sidorenko's conjecture. ErdH{o}s and S'os asked what the maximum number of rainbow triangles is in a $3$-coloring of the edge set of $K_n$, a rainbow version of the Ramsey multiplicity question. A graph $H$ is called $r$-anti-common if the maximum proportion of rainbow copies of $H$ in any $r$-coloring of $E(K_n)$ is asymptotically achieved by taking a random coloring. In this paper, we investigate anti-Ramsey multiplicity for several families of graphs. We determine classes of graphs which are either anti-common or not. Some of these classes follow the same behavior as the monochromatic case, but some of them do not. In particular the rainbow equivalent of Sidorenko's conjecture, that all bipartite graphs are anti-common, is false.

Recommendations

• scientific article; zbMATH DE number 3494450
• scientific article; zbMATH DE number 426321
• Anti-Ramsey hypergraph numbers
• On degree anti-Ramsey numbers
• A Ramsey theorem for multiposets
• An anti-Ramsey theorem
• An anti-Ramsey theorem
• On a generalized anti-Ramsey problem
• Ramsey multiplicities of some graphs
• Anti-Ramsey number of matchings in hypergraphs

Cites work

• A correlation inequality for bipartite graphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• An approximate version of Sidorenko's conjecture
• Cycles in graphs and functional inequalities
• Graph norms and Sidorenko's conjecture
• Graphs containing triangles are not 3-common
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• Monochromatic triangles in three-coloured graphs
• Multiplicities of subgraphs
• On Sets of Acquaintances and Strangers at any Party
• On the Ramsey multiplicities of graphs—problems and recent results
• On the Ramsey multiplicity for stars
• There exist graphs with super‐exponential Ramsey multiplicity constant
• Two approaches to Sidorenko's conjecture

Cited in

(7)

• Multi-dimensional Ramsey theorems -- an example
• Anti-Ramsey colorings in several rounds
• Indicators, chains, antichains, Ramsey property
• On tripartite common graphs
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• Bounds for rainbow-uncommon graphs
• Rainbow common graphs must be forests

This page was built for publication: Anti-Ramsey Multiplicities

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