Metraipolis › archive › dc_f3da98740bb1

Global and local degree conditions for matchability — arXiv:2609.07161

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.07161
License (as archived)
CC0-1.0
Archived
2026-10-16T14:48:44.137Z
SHA-256 of the archived text
078fd78619023ce151f77ddaa61cb578a4a7845e1fabd626fcf54e33be556be4
Stable URL of this page
https://metraipolis.com/documento/dc_f3da98740bb1

How to cite

Global and local degree conditions for matchability — arXiv:2609.07161 — arXiv (en), https://arxiv.org/abs/2609.07161 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f3da98740bb1 (Metraipolis archive dc_f3da98740bb1, sha256 078fd78619023ce151f77ddaa61cb578a4a7845e1fabd626fcf54e33be556be4)
BibTeX
@misc{dcf3da98740bb1,
  title = {Global and local degree conditions for matchability — arXiv:2609.07161},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.07161},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f3da98740bb1; sha256 078fd78619023ce151f77ddaa61cb578a4a7845e1fabd626fcf54e33be556be4},
  year = {2026}
}

Archived text

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

A corollary of Hall's marriage theorem is that a sufficient condition for a list $(V_1, \ldots ,V_m)$ of sets to have a system of distinct representatives is that $|V_i|\ge deg_{\{V_1, \ldots ,V_m\}}(v)$ for every $i\in [m]$ and $v \in \bigcup_{i\in [m]}V_i$. This we dub a {\em global} condition. A folklore result is that a {\em local} condition - that the inequality holds for pairs $i,v$ for which $v \in V_i$ - suffices. These are special cases of a general type of results - large sets, whose elements are sparse in some sense, have a system of representatives that is independent in a related graph. We study two such scenarios, in both of which each $V_i$ is replaced by a $k$-uniform hypergraph $H_i$, the representatives are hyperedges, and distinctness is replaced by disjointness. In one setting the sparsity is measured by the degrees of vertices in the hypergraphs, in the other by the degrees of vertices in the line graph. The proofs use the topological version of Hall's theorem. In particular, we shall use a lower bound on the topological connectivity of the independence complex of a graph, defined by vector representations. We also provide short proofs of the local infinite version, known as the ``Milner-Shelah theorem''.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.07161 — 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-16T14:32:29.814Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).