Regular bipartite decompositions of pseudorandom 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_ | 1866914975766806528 |
|---|---|
| author | Ferber, Asaf Frederickson, Bryce Mao, Dingjia Yepremyan, Liana Zhu, Yizhe |
| author_facet | Ferber, Asaf Frederickson, Bryce Mao, Dingjia Yepremyan, Liana Zhu, Yizhe |
| contents | In 1972, Kotzig proved that for every even $n$, the complete graph $K_n$ can be decomposed into $\lceil\log_2n\rceil$ edge-disjoint regular bipartite spanning subgraphs, which is best possible. In this paper, we study regular bipartite decompositions of $(n,d,λ)$-graphs, where $n$ is an even integer and $d_0\leq d\leq n-1$ for some absolute constant $d_0$. With a randomized algorithm, we prove that such an $(n,d,λ)$-graph with $λ\leq d/12$ can be decomposed into at most $\log_2 d + 36$ regular bipartite spanning subgraphs. This is best possible up to the additive constant term. As a consequence, we also improve the best known bounds on $λ= λ(d)$ by Ferber and Jain (2020) to guarantee that an $(n,d,λ)$-graph on an even number of vertices admits a $1$-factorization, showing that $λ\leq cd$ is sufficient for some absolute constant $c > 0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12981 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Regular bipartite decompositions of pseudorandom graphs Ferber, Asaf Frederickson, Bryce Mao, Dingjia Yepremyan, Liana Zhu, Yizhe Combinatorics 05C80 (Primary) 05C48, 05C85 (Secondary) In 1972, Kotzig proved that for every even $n$, the complete graph $K_n$ can be decomposed into $\lceil\log_2n\rceil$ edge-disjoint regular bipartite spanning subgraphs, which is best possible. In this paper, we study regular bipartite decompositions of $(n,d,λ)$-graphs, where $n$ is an even integer and $d_0\leq d\leq n-1$ for some absolute constant $d_0$. With a randomized algorithm, we prove that such an $(n,d,λ)$-graph with $λ\leq d/12$ can be decomposed into at most $\log_2 d + 36$ regular bipartite spanning subgraphs. This is best possible up to the additive constant term. As a consequence, we also improve the best known bounds on $λ= λ(d)$ by Ferber and Jain (2020) to guarantee that an $(n,d,λ)$-graph on an even number of vertices admits a $1$-factorization, showing that $λ\leq cd$ is sufficient for some absolute constant $c > 0$. |
| title | Regular bipartite decompositions of pseudorandom graphs |
| topic | Combinatorics 05C80 (Primary) 05C48, 05C85 (Secondary) |
| url | https://arxiv.org/abs/2410.12981 |