umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Multicolor containers, extremal entropy, and counting
Umeå University.
2019 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 54, no 4, p. 676-720Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Wiley-Blackwell, 2019. Vol. 54, no 4, p. 676-720
Keywords [en]
entropy, extremal graph theory, hereditary property, hypergraph container method
National Category
Computer Sciences Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-161443DOI: 10.1002/rsa.20777ISI: 000470931400005OAI: oai:DiVA.org:umu-161443DiVA, id: diva2:1336754
Funder
Swedish Research CouncilAvailable from: 2019-07-10 Created: 2019-07-10 Last updated: 2019-07-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Falgas-Ravry, Victor

Search in DiVA

By author/editor
Falgas-Ravry, Victor
By organisation
Umeå University
In the same journal
Random structures & algorithms (Print)
Computer SciencesDiscrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 20 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf