Asymptotic enumeration via graph containers and entropy
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909940429357056 |
|---|---|
| author | Park, Jinyoung |
| author_facet | Park, Jinyoung |
| contents | The container methods are powerful tools to bound the number of independent sets of graphs and hypergraphs, and they have been extremely influential in the area of extremal and probabilistic combinatorics. We will focus on more specialized graph container methods due to Sapozhenko (1987) that deal with sets in expander graphs. Entropy, first introduced by Shannon (1948) in the area of information theory, is a measure of the expected amount of information contained in a random variable. Entropy has seen lots of fascinating applications in a wide range of enumeration problems. In this survey article, we will discuss recent developments that exploit a combination of the two methods on enumerating graph homomorphisms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02995 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic enumeration via graph containers and entropy Park, Jinyoung Combinatorics The container methods are powerful tools to bound the number of independent sets of graphs and hypergraphs, and they have been extremely influential in the area of extremal and probabilistic combinatorics. We will focus on more specialized graph container methods due to Sapozhenko (1987) that deal with sets in expander graphs. Entropy, first introduced by Shannon (1948) in the area of information theory, is a measure of the expected amount of information contained in a random variable. Entropy has seen lots of fascinating applications in a wide range of enumeration problems. In this survey article, we will discuss recent developments that exploit a combination of the two methods on enumerating graph homomorphisms. |
| title | Asymptotic enumeration via graph containers and entropy |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.02995 |