Metraipolis › archive › dc_7902a82e54df

A Necessary and Sufficient Hall Condition for Hypergraphs — arXiv:2608.10193

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.10193
License (as archived)
CC0-1.0
Archived
2026-10-19T06:27:22.340Z
SHA-256 of the archived text
d9397e19e6d5d0ca14e968484486c9b07785b4f9d29054b687f898708b78c56f
Stable URL of this page
https://metraipolis.com/documento/dc_7902a82e54df

How to cite

A Necessary and Sufficient Hall Condition for Hypergraphs — arXiv:2608.10193 — arXiv (en), https://arxiv.org/abs/2608.10193 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7902a82e54df (Metraipolis archive dc_7902a82e54df, sha256 d9397e19e6d5d0ca14e968484486c9b07785b4f9d29054b687f898708b78c56f)
BibTeX
@misc{dc7902a82e54df,
  title = {A Necessary and Sufficient Hall Condition for Hypergraphs — arXiv:2608.10193},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.10193},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7902a82e54df; sha256 d9397e19e6d5d0ca14e968484486c9b07785b4f9d29054b687f898708b78c56f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.10193. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We prove a necessary and sufficient Hall condition for a family $A=(A_e)_{e\in E(G)}$ of hypergraphs indexed by the edges of a forest \(G\). This restriction on the index graph is sharp. The loop-only case recovers the classical Hall's Theorem with multiplicities for arbitrary finite set systems, while the loopless case shows that full rainbow matching is polynomial time solvable under this forest structure, although the problem is NP-complete in general. As another application, we prove every $5$-tough chordal graph is Hamilton-connected, improving toughness bounds of $18$ for Hamiltonicity (1998) and $10$ for Hamilton-connectedness (2017).

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-12 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.10193 — 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-19T06:20:30.682Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-12?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).