Global and local degree conditions for matchability
Abstract
A corollary of Hall's marriage theorem is that a sufficient condition for a list (V1, … ,Vm) of sets to have a system of distinct representatives is that |Vi|≥ deg{V1, … ,Vm}(v) for every i∈ [m] and v ∈ ⋃i∈ [m]Vi. 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 ∈ Vi - 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 Vi is replaced by a k-uniform hypergraph Hi, 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''.
Related
- Local versus global average degree in bipartite graphs
- Ore-degree conditions for hypergraph matchings
- Degree conditions for k-strong orientations of digraphs
- Size and spectral radius conditions for the existence of k-factor in graphs with given minimum degree
- Global minimality of the degree-one Ginzburg-Landau vortex solution in the unit ball in dimensions n ≥ 2
BibTeX
@misc{aharoni2026global,
title = {{Global and local degree conditions for matchability}},
author = {Ron Aharoni and Eli Berger and Attila Joó},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07161},
eprint = {2609.07161},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07161},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Global and local degree conditions for matchability
AU - Ron Aharoni
AU - Eli Berger
AU - Attila Joó
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07161
UR - https://arxiv.org/abs/2609.07161
AB - A corollary of Hall's marriage theorem is that a sufficient condition for a list (V_1, … ,V_m) of sets to have a system of distinct representatives is that |V_i|≥ deg_{V_1, … ,V_m}(v) for every i∈ [m] and v ∈ ⋃_i∈ [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 ∈ 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''.
ER -