Metraipolis › archive › dc_ff86a75f8701
Exact three-component covers in 2-coloured random bipartite graphs — arXiv:2609.17567
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.17567
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T16:12:59.644Z
- SHA-256 of the archived text
975793bd5ad9616479976a89333234c20938c004a5f6a6e263ff1202a8277d85- Stable URL of this page
https://metraipolis.com/documento/dc_ff86a75f8701
How to cite
Exact three-component covers in 2-coloured random bipartite graphs — arXiv:2609.17567 — arXiv (en), https://arxiv.org/abs/2609.17567 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ff86a75f8701 (Metraipolis archive dc_ff86a75f8701, sha256 975793bd5ad9616479976a89333234c20938c004a5f6a6e263ff1202a8277d85)
BibTeX
@misc{dcff86a75f8701,
title = {Exact three-component covers in 2-coloured random bipartite graphs — arXiv:2609.17567},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.17567},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ff86a75f8701; sha256 975793bd5ad9616479976a89333234c20938c004a5f6a6e263ff1202a8277d85},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.17567. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We resolve the two-colour three-component conjecture of Fernández, Pavez-Signé and Stein for random bipartite graphs. More precisely, we prove that if $G\sim G(n,n,p)$ and $p\gg\sqrt{\log n/n}$, then with high probability every red--blue edge-colouring of $G$ admits a cover of its vertex set by at most three monochromatic connected components. The proof is based on a uniform expansion lemma for unions of common neighbourhoods and an alternating common-neighbourhood expansion argument.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.17567 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T15:38:58.213Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).