Extending the notion of (random) $k$-out graphs, we consider when the $k$-out hypergraph is likely to have a perfect fractional matching. In particular, we show that for each $r$ there is a $k=k(r)$ such that the $k$-out $r$-uniform hypergraph on $n$ vertices has a perfect fractional matching with high probability (i.e., with probability tending to $1$ as $n\to\infty$) and prove an analogous result for $r$-uniform $r$-partite hypergraphs. This is based on a new notion of hypergraph expansion and the observation that sufficiently expansive hypergraphs admit perfect fractional matchings. As a further application, we give a short proof of a stopping-time result originally due to Krivelevich.
@article{10_37236_6890,
author = {Pat Devlin and Jeff Kahn},
title = {Perfect fractional matchings in \(k\)-out hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {3},
doi = {10.37236/6890},
zbl = {1372.05197},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6890/}
}
TY - JOUR
AU - Pat Devlin
AU - Jeff Kahn
TI - Perfect fractional matchings in \(k\)-out hypergraphs
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/6890/
DO - 10.37236/6890
ID - 10_37236_6890
ER -
%0 Journal Article
%A Pat Devlin
%A Jeff Kahn
%T Perfect fractional matchings in \(k\)-out hypergraphs
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/6890/
%R 10.37236/6890
%F 10_37236_6890
Pat Devlin; Jeff Kahn. Perfect fractional matchings in \(k\)-out hypergraphs. The electronic journal of combinatorics, Tome 24 (2017) no. 3. doi: 10.37236/6890
