EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

Regular bipartite decompositions of pseudorandom graphs

Asaf Ferber, Bryce Frederickson, Dingjia Mao, Liana Yepremyan, Yizhe Zhu

Journal of Combinatorial Theory, Series B · 2026-07 · 179 · 270-292

DOI: 10.1016/j.jctb.2026.04.004 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Combinatorial Theory, Series B, 2026-07. Verfasst von Asaf Ferber und 4 weiteren Autor:innen. Die Arbeit nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0). Gefördert von: US Air Force, American Mathematical Society, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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,\lambda)$-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,\lambda)$-graph with $\lambda\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 $\lambda = \lambda(d)$ by Ferber and Jain (2020) to guarantee that an $(n,d,\lambda)$-graph on an even number of vertices admits a $1$-factorization, showing that $\lambda \leq cd$ is sufficient for some absolute constant $c>0$.

Förderung

  • US Air Force
  • American Mathematical Society
  • National Science Foundation

Zitieren

APA

Ferber, A., Frederickson, B., Mao, D., Yepremyan, L., & Zhu, Y. (2026). Regular bipartite decompositions of pseudorandom graphs. Journal of Combinatorial Theory, Series B, 179, 270-292. https://doi.org/10.1016/j.jctb.2026.04.004

Vancouver

Ferber A, Frederickson B, Mao D, Yepremyan L, Zhu Y. Regular bipartite decompositions of pseudorandom graphs. Journal of Combinatorial Theory, Series B. 2026;179:270-292. doi:10.1016/j.jctb.2026.04.004

BibTeX
@article{Ferber2026,
  author = {Ferber, Asaf and Frederickson, Bryce and Mao, Dingjia and Yepremyan, Liana and Zhu, Yizhe},
  title = {Regular bipartite decompositions of pseudorandom graphs},
  journal = {Journal of Combinatorial Theory, Series B},
  year = {2026},
  volume = {179},
  pages = {270--292},
  doi = {10.1016/j.jctb.2026.04.004}
}
Kostenlos starten →