Packing large balanced trees into bipartite graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916442726727680 |
|---|---|
| author | Fernandes, Cristina G. Naia, Tássio Santos, Giovanne Stein, Maya |
| author_facet | Fernandes, Cristina G. Naia, Tássio Santos, Giovanne Stein, Maya |
| contents | We prove that for every ${γ> 0}$ there exists $n_0 \in \mathbb{N}$ such that for every ${n \geq n_0}$ any family of up to $\lfloor{n^{\frac12+γ}}\rfloor$ trees having at most $(1-γ)n$ vertices in each bipartition class can be packed into $K_{n,n}$. As a tool for our proof, we show an approximate bipartite version of the Komlós-Sárközy-Szemerédi Theorem, which we believe to be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_13290 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Packing large balanced trees into bipartite graphs Fernandes, Cristina G. Naia, Tássio Santos, Giovanne Stein, Maya Combinatorics We prove that for every ${γ> 0}$ there exists $n_0 \in \mathbb{N}$ such that for every ${n \geq n_0}$ any family of up to $\lfloor{n^{\frac12+γ}}\rfloor$ trees having at most $(1-γ)n$ vertices in each bipartition class can be packed into $K_{n,n}$. As a tool for our proof, we show an approximate bipartite version of the Komlós-Sárközy-Szemerédi Theorem, which we believe to be of independent interest. |
| title | Packing large balanced trees into bipartite graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.13290 |