Multicolor containers, extremal entropy, and counting

DOI10.1002/RSA.20777MaRDI QIDQ5229338zbMATH OpenOpenAlexWikidataFDO

Authors Victor Falgas-Ravry, Kelly O'Connell, Andrew J. Uzzell

Publication date 14 August 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

entropyextremal graph theoryhereditary propertyhypergraph container method

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Abstract: In breakthrough results, Saxton-Thomason and Balogh-Morris-Samotij developed powerful theories of hypergraph containers. In this paper, we explore some consequences of these theories. We use a simple container theorem of Saxton-Thomason and an entropy-based framework to deduce container and counting theorems for hereditary properties of k-colourings of very general objects, which include both vertex- and edge-colourings of general hypergraph sequences as special cases. In the case of sequences of complete graphs, we further derive characterisation and transference results for hereditary properties in terms of their stability families and extremal entropy. This covers within a unified framework a great variety of combinatorial structures, some of which had not previously been studied via containers: directed graphs, oriented graphs, tournaments, multigraphs with bounded multiplicity and multicoloured graphs amongst others. Similar results were recently and independently obtained by Terry.

Recommendations

• Counting colorings on varieties
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Counting and sampling \(H\)-colourings
• scientific article; zbMATH DE number 2019624
• On maximal quantity of particles of one color in analogs of multicolor urn schemes
• Multicoloured extremal problems
• The \(n\)-color partition function and some counting theorems
• A quantitative variant of the multi-colored Motzkin-Rabin theorem
• On counting generalized colorings

Cited in

(11)

• Integer colorings with no rainbow 3-term arithmetic progression
• Integer colorings with no rainbow \(k\)-term arithmetic progression
• Multicolor chain avoidance in the Boolean lattice
• Extremal problems for multigraphs
• Independent sets in hypergraphs and Ramsey properties of graphs and the integers
• Rainbow Erdös-Rothschild problem for the Fano plane
• Extremal theory of locally sparse multigraphs
• The Typical Structure of Gallai Colorings and Their Extremal Graphs
• Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers
• Integer colorings with forbidden rainbow sums
• On an extremal problem for locally sparse multigraphs

This page was built for publication: Multicolor containers, extremal entropy, and counting

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