Multicolor containers, extremal entropy, and counting. Issue 4 (6th April 2018)

• Record Type: Journal Article
• Authors: Falgas‐Ravry, Victor; O'Connell, Kelly; Uzzell, Andrew
• Is Part Of: Random structures & algorithms. Volume 54:Issue 4(2019)
• Page Start: 676
• Page End: 720
• Publication Date: 2018-04-06
• Subjects: entropy -- extremal graph theory -- hereditary property -- hypergraph container method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20777
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ‐colorings of very general objects, which include both vertex‐ and edge‐colorings of general hypergraph sequences as special cases. In the case of sequences of complete graphs, we further derive characterization 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 multicolored graphs among others. Similar results were recently and independently obtained by Terry.