Kruskal--Katona-Type Problems via the Entropy Method
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917842700468224 |
|---|---|
| author | Chao, Ting-Wei Yu, Hung-Hsun Hans |
| author_facet | Chao, Ting-Wei Yu, Hung-Hsun Hans |
| contents | In this paper, we investigate several extremal combinatorics problems that ask for the maximum number of copies of a fixed subgraph given the number of edges. We call problems of this type Kruskal--Katona-type problems. Most of the problems that will be discussed in this paper are related to the joints problem. There are two main results in this paper. First, we prove that, in a $3$-edge-colored graph with $R$ red, $G$ green, $B$ blue edges, the number of rainbow triangles is at most $\sqrt{2RGB}$, which is sharp. Second, we give a generalization of the Kruskal--Katona theorem that implies many other previous generalizations. Both arguments use the entropy method, and the main innovation lies in a more clever argument that improves bounds given by Shearer's inequality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_15379 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Kruskal--Katona-Type Problems via the Entropy Method Chao, Ting-Wei Yu, Hung-Hsun Hans Combinatorics Information Theory 05D05, 05D40, 94A17 In this paper, we investigate several extremal combinatorics problems that ask for the maximum number of copies of a fixed subgraph given the number of edges. We call problems of this type Kruskal--Katona-type problems. Most of the problems that will be discussed in this paper are related to the joints problem. There are two main results in this paper. First, we prove that, in a $3$-edge-colored graph with $R$ red, $G$ green, $B$ blue edges, the number of rainbow triangles is at most $\sqrt{2RGB}$, which is sharp. Second, we give a generalization of the Kruskal--Katona theorem that implies many other previous generalizations. Both arguments use the entropy method, and the main innovation lies in a more clever argument that improves bounds given by Shearer's inequality. |
| title | Kruskal--Katona-Type Problems via the Entropy Method |
| topic | Combinatorics Information Theory 05D05, 05D40, 94A17 |
| url | https://arxiv.org/abs/2307.15379 |