Further applications of the Container Method
| Autor: | Adam Zsolt Wagner, József Balogh |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Random graph 010102 general mathematics Szemerédi regularity lemma 0102 computer and information sciences 01 natural sciences Combinatorics Metric space Cardinality 010201 computation theory & mathematics Container (abstract data type) A priori and a posteriori 0101 mathematics Mathematics |
| Zdroj: | Recent Trends in Combinatorics ISBN: 9783319242965 |
| DOI: | 10.1007/978-3-319-24298-9_8 |
| Popis: | Recently, Balogh–Morris–Samotij and Saxton–Thomason proved that hypergraphs satisfying some natural conditions have only few independent sets. Their main results already have several applications. However, the methods of proving these theorems are even more far reaching. The general idea is to describe some family of events, whose cardinality a priori could be large, only with a few certificates. Here, we show some applications of the methods, including counting C4-free graphs, considering the size of a maximum C4-free subgraph of a random graph and counting metric spaces with a given number of points. Additionally, we discuss some connections with the Szemeredi Regularity Lemma. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|