\documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.60}{24(3)}{2017} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsmath,amsthm,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\E}[0]{\mathbb{E}} %\newcommand{\EE}{\mathcal E} \newcommand{\qq}[0]{d} \newtheorem{Theorem}{Theorem}[section] \newtheorem{lemma}[Theorem]{Lemma} \newcommand{\beq}[1]{\begin{equation}\label{#1}} \newcommand{\enq}[0]{\end{equation}} \newcommand{\bn}[0]{\bigskip\noindent} \newcommand{\mn}[0]{\medskip\noindent} \newcommand{\nin}[0]{\noindent} \newcommand{\sub}[0]{\subseteq} \newcommand{\sm}[0]{\setminus} \renewcommand{\dots}[0]{,\ldots,} \renewcommand{\iff}[0]{\Longleftrightarrow} \newcommand{\ov}[0]{\overline} \newcommand{\un}[0]{\underline} \newcommand{\less}[0]{~~\mbox{\raisebox{-.6ex}{$\stackrel{\textstyle{<}}{\sim}$}}~~} \newcommand{\more}[0]{~~\mbox{\raisebox{-.6ex}{$\stackrel{\textstyle{>}}{\sim}$}}~~} \newcommand{\A}[0]{{\cal A}} \newcommand{\B}[0]{{\cal B}} \newcommand{\cee}[0]{{\cal C}} \newcommand{\D}[0]{{\cal D}} \newcommand{\eee}[0]{{\cal E}} \newcommand{\f}[0]{{\cal F}} \newcommand{\g}[0]{{\cal G}} \newcommand{\h}[0]{{\cal H}} \newcommand{\I}[0]{{\cal I}} \newcommand{\J}[0]{{\cal J}} \newcommand{\K}[0]{{\cal K}} \newcommand{\Ll}[0]{{\cal L}} \newcommand{\m}[0]{{\cal M}} \newcommand{\N}[0]{{\cal N}} \newcommand{\Oh}[0]{{\cal O}} \newcommand{\pee}[0]{{\cal P}} \newcommand{\Q}[0]{{\cal Q}} \newcommand{\Qq}[0]{{\cal Q}^*} \newcommand{\R}[0]{{\cal R}} \newcommand{\sss}[0]{{\cal S}} \newcommand{\T}[0]{{\cal T}} \newcommand{\U}[0]{{\cal U}} \newcommand{\W}[0]{{\cal W}} \newcommand{\X}[0]{{\cal X}} \newcommand{\Y}[0]{{\cal Y}} \newcommand{\ZZZ}[0]{{\cal Z}} \newcommand{\ab}[0]{s} \newcommand{\ra}[0]{\rightarrow} \newcommand{\Ra}[0]{\Rightarrow} \newcommand{\lra}[0]{\leftrightarrow} \newcommand{\Lra}[0]{\Leftrightarrow} \newcommand{\nrar}{\hspace{.03in}\not\hspace{-.08in}\longleftrightarrow} \newcommand{\CC}[0]{{\bf C}} \newcommand{\ZZ}[0]{{\bf Z}} %\newcommand{\EE}[0]{{\bf E}} \newcommand{\FF}[0]{{\bf F}} \newcommand{\ff}[0]{{\bf f}} \newcommand{\GG}[0]{{\bf G}} \newcommand{\HH}[0]{{\bf H}} \newcommand{\II}[0]{{\bf I}} \newcommand{\KK}[0]{{\bf K}} \newcommand{\MM }[0]{{\bf M}} \newcommand{\PP}[0]{{\bf P}} \newcommand{\RR}[0]{\mbox{${\bf R}^+$}} \newcommand{\Rr}[0]{\mbox{${\bf R}$}} \newcommand{\TT}[0]{{\bf T}} \newcommand{\Nn}[0]{{\bf N}} \newcommand{\VV}[0]{{\bf V}} \newcommand{\XX}[0]{{\sf X}}%{{\bf X}} \newcommand{\crit}[0]{{\rm crit}} \newcommand{\ext}[0]{{\rm ext}} \newcommand{\deff}[0]{{\rm def}} \newcommand{\core}[0]{{\rm core}} \newcommand{\xx}[0]{{\bf x}} \newcommand{\bb}[0]{b} %\newcommand{\cc}[0]{\mbox{{\sf c}}} \newcommand{\cc}[0]{\gamma} \newcommand{\ddd}[0]{\mbox{{\sf d}}} \newcommand{\ttt}[0]{t} \renewcommand{\tt}[0]{\mbox{{\sf t}}} \newcommand{\aaa}[0]{a} \newcommand{\bbb}[0]{\mbox{{\sf b}}} \newcommand{\ww}{\mbox{{\sf w}}} \newcommand{\zz}[0]{\mbox{{\sf z}}} \newcommand{\llll}[0]{l} \newcommand{\RRR}[0]{C} \newcommand{\0}[0]{\emptyset} %\renewcommand{\qed}[0]{\begin{flushright} \rule{2mm}{3mm} \end{flushright}} \def\qqed{\null\nobreak\hfill\hbox{${\diamondsuit}$}\par\smallskip} \def\qqqed{\null\nobreak\hfill\hbox{\rule{2mm}{3mm} }\par\smallskip} \def\proofend{\hfill$\box$\medskip} \newcommand{\C}[2]{{{#1}\choose{{#2}}}} \newcommand{\Cc}[0]{\tbinom} \newcommand{\ga}[0]{\alpha } \newcommand{\gb}[0]{\beta } \newcommand{\gc}[0]{\gamma } \newcommand{\gd}[0]{\delta } \newcommand{\gD}[0]{\Delta } \newcommand{\gG}[0]{\Gamma } \newcommand{\gk}[0]{\kappa } \newcommand{\gl}[0]{\lambda } \newcommand{\gL}[0]{\Lambda} \newcommand{\go}[0]{\omega} \newcommand{\gO}[0]{\Omega} \newcommand{\gdi}[0]{\delta_i } \newcommand{\gli}[0]{\lambda_i } \newcommand{\gs}[0]{\sigma} \newcommand{\gS}[0]{\Sigma} \newcommand{\gz}[0]{\zeta} \newcommand{\eps}[0]{\varepsilon } \newcommand{\vt}[0]{\vartheta} \newcommand{\vs}[0]{\varsigma} \newcommand{\vr}[0]{\varrho} \newcommand{\vp}[0]{\varphi} \newcommand{\Ups}[0]{\Upsilon} %\newcommand{\1}[0]{{\bf 1}} \newcommand{\rrr}[0]{r} \newcommand{\ft}[0]{s} \newcommand{\fP}[0]{f} \newcommand{\hr}[0]{\hat{r}} \newcommand{\sugr}[1]{\mn\textcolor{Red}{[#1]}} %\newcommand{\sugr}[1]{} %\newcommand{\sugg}[1]{\mn{\bf [#1]}} %\newcommand{\sugg}[1]{} \newcommand{\sugb}[1]{\mn \textcolor{NavyBlue}{[#1]}} %\newcommand{\sugb}[1]{} \newcommand{\redd}[1]{\textcolor{Red}{#1}} \newcommand{\red}[1]{\textcolor{Red}{[#1]}} %\newcommand{\red}[1]{} \newcommand{\blue}[1]{\textcolor{Blue}{#1}} \newcommand{\bblue}[1]{\textcolor{Blue}{[#1]}} \newcommand{\pur}[1]{\textcolor{Purple}{#1}} \newcommand{\Pur}[1]{\textcolor{Purple}{[#1]}} \newcommand{\sugp}[1]{\mn\textcolor{Purple}{[#1]}} \newcommand{\green}[1]{\textcolor{Magenta}{#1}} \newcommand{\comments}[1]{} \usepackage[usenames]{color} \newcommand{\pr}[1][]{\mathbb{P}} \newcommand{\mean}[1]{\mathbb{E}\left[{#1}\right]} \newcommand{\Ee}{\mathcal{E}} \newcommand{\Ef}{\mathcal{F}} \newcommand{\Gee}{\mathcal{G}} \newcommand{\Aitch}{\mathcal{H}} \newcommand{\Jay}{\mathcal{J}} \newcommand{\Em}{\mathcal{M}} \newcommand{\Pee}{\mathcal{P}} \newcommand{\AitchOut}[3]{\Aitch_{#1, #3} ^{#2\text{-out}}} \newcommand{\MPOut}[3]{\kout{\mpart{#1}{#3}}{#2}} \newcommand{\kout}[2]{{#1}(#2\text{-out})} \newcommand{\complete}[2]{K_{#1} ^{(#2)}} \newcommand{\mpart}[2]{K_{[{#1}] ^{#2}}} \newcommand{\flo}[1]{\left \lfloor #1 \right \rfloor} \newcommand{\cel}[1]{\left \lceil #1 \right \rceil} \newcommand{\inte}[1]{\mathrm{int}(#1)} \newcommand{\cho}[2]{\begin{pmatrix}#1\\#2\end{pmatrix}} \newcommand{\lcho}[2]{{#1 \choose #2}} \newcommand{\bigO}[1]{\mathcal{O}\left(#1\right)} \newcommand{\littleO}[1]{o\left(#1\right)} \newcommand{\1}{\textbf{1}} \newcommand{\ignore}[1]{} \newcommand{\pder}[2]{\dfrac{\partial #1}{\partial #2}} \newcommand{\dd}[1]{\,\textit{d}#1} \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \iffalse %\newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{corollary}[theorem]{Corollary} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\E}{\mathbb{E}} \newcommand{\N}{\mathbb{N}} \newcommand{\D}{\mathbb{D}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\im}{\text{Im}\,} \newcommand{\re}{\text{Re}\,} \newcommand{\Res}{\text{Res}} \newcommand{\prob}{\mathbb{P}} \newcommand{\Var}{\text{Var}} \newcommand{\Ee}{\mathcal{E}} \newcommand{\Ef}{\mathcal{F}} \newcommand{\Gee}{\mathcal{G}} \newcommand{\Aitch}{\mathcal{H}} \newcommand{\Jay}{\mathcal{J}} \newcommand{\Em}{\mathcal{M}} \newcommand{\Pee}{\mathcal{P}} \newcommand{\AND}{\wedge} \newcommand{\OR}{\vee} \newcommand{\cha}{\text{char}} \newcommand{\pder}[2]{\dfrac{\partial #1}{\partial #2}} \newcommand{\dd}[1]{\,\textit{d}#1} \newcommand{\flo}[1]{\left \lfloor #1 \right \rfloor} \newcommand{\cel}[1]{\left \lceil #1 \right \rceil} \newcommand{\inte}[1]{\mathrm{int}(#1)} \newcommand{\pr}{\mathbb{P}} \newcommand{\cho}[2]{\begin{pmatrix}#1\\#2\end{pmatrix}} \newcommand{\lcho}[2]{{#1 \choose #2}} \newcommand{\bigO}[1]{\mathcal{O}\left(#1\right)} \newcommand{\littleO}[1]{o\left(#1\right)} \newcommand{\1}{\textbf{1}} \newcommand{\ignore}[1]{} \newcommand{\AitchOut}[3]{\Aitch_{#1, #3} ^{#2\text{-out}}} \newcommand{\MPOut}[3]{\kout{\mpart{#1}{#3}}{#2}} \newcommand{\kout}[2]{{#1}(#2\text{-out})} \newcommand{\complete}[2]{K_{#1} ^{(#2)}} \newcommand{\mpart}[2]{K_{[{#1}] ^{#2}}} \newcommand{\red}[1]{{\color{red}#1}} \newcommand{\redd}[1]{\textcolor{red}{#1}} %%%%%%%%%%%%%%%more: \newcommand{\h}[0]{{\cal H}} \fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{siam} \begin{document} \renewcommand{\thefootnote}{\fnsymbol{footnote}} %05C65 [hypergraphs], 05C70 [matchings], 05C72 [fractional graph theory, fuzzy graphs], 05C80 [random graphs], 05D40 [prob methods], 90C05 [linear programming] % %\footnotetext{AMS 2010 subject classification: 05C65, 05C70, 05D40, 05C80, 90C05, 90C32} \title{\bf Perfect fractional matchings in $k$-out hypergraphs\footnote{Supported by NSF grant DMS1501962.}} \author{Pat Devlin \quad \quad Jeff Kahn\\ \small Department of Mathematics \\[-0.8ex] \small Rutgers University\\[-0.8ex] \small Piscataway, NJ, U.S.A.\\ \small\texttt{ \{prd41, jkahn\}@math.rutgers.edu}} \date{\dateline{Mar 13, 2017}{Sep 5, 2017}{Sep 22, 2017}\\ \small Mathematics Subject Classifications: 05C65; 05C70; 05D40; 05C80; 90C05; 90C32} \maketitle \renewcommand*{\thefootnote}{\arabic{footnote}} \begin{abstract} 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\ra\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. \bigskip\noindent \textbf{Keywords:} random hypergraphs, perfect fractional matchings, k-out model, hypergraph expansion \end{abstract} \section{Introduction} Hypergraphs constitute a far-reaching generalization of graphs and a basic combinatorial construct but are notoriously difficult to work with. A \textit{hypergraph} is a collection $\Aitch$ of subsets (\emph{``edges"}) of a set $V$ of \emph{``vertices."} Such an $\Aitch$ is $r$-\emph{uniform} (or an \emph{r-graph}) if each edge has cardinality $r$ (so $2$-graphs are graphs). A \textit{perfect matching} in a hypergraph is a collection of edges partitioning the vertex set. For any $r > 2$, deciding whether an $r$-graph has a perfect matching is an NP-complete problem \cite{karp}; so instances of the problem tend to be both interesting and difficult. Of particular interest here has been trying to understand conditions under which a \emph{random} hypergraph is likely to have a perfect matching. \mn The most natural model of a random $r$-graph is the ``Erd\H{o}s-R\'enyi" model, in which each $r$-set is included in $\Aitch$ with probability $p$, independent of other choices. One is then interested in the ``threshold," roughly, the order of magnitude of $p=p_r(n)$ required to make a perfect matching likely. Here the graph case was settled by Erd\H{o}s and R\'enyi \cite{erdos1964random, erd1966}, but for $r > 2$ the problem---which became known as Shamir's Problem following \cite{erdos1981combinatorial}---remained open until \cite{johansson2008factors}. In each case, the obvious obstruction to containing a perfect matching is existence of an isolated vertex (that is, a vertex contained in no edges), and a natural guess is that this is the \emph{main} obstruction. A literal form of this assertion---the \emph{stopping time} version---says that if we choose random edges \emph{sequentially}, each uniform from those as yet unchosen, then we w.h.p.\footnote{As usual we use \emph{with high probability (w.h.p.)}\ to mean with probability tending to 1 as the relevant parameter---here always $n$---tends to infinity.}\ have a perfect matching as soon as all vertices are covered. This nice behavior does hold for graphs \cite{bollobas1985random}, but for hypergraphs remains conjectural (though at least the value it suggests for the threshold is correct). \mn An interesting point here is that taking $p$ large enough to avoid isolated vertices produces many more edges than other considerations---e.g., wanting a large \emph{expected} number of perfect matchings---suggest. This has been one motivation for the substantial body of work on models of random graphs in which isolated vertices are automatically avoided, notably random \emph{regular} graphs (e.g., \cite{wormald1999models}) and the $k$-out model. The generalization of the latter to hypergraphs, which we now introduce, will be our main focus here. \begin{quote} \textbf{The $k$-out model.} For a (``host") hypergraph $\h$ on $V$, $\kout{\h}{k}$ is the random subhypergraph $\cup_{v\in V}E_v$, where $E_v$ is chosen uniformly from the $k$-subsets of $\h_v:=\{A\in \h:v\in A\}$ (or---but we won't see this---$E_v =\h_v$ if $|\h_v|2$ the proof of this can be tweaked to give the stronger conclusion even under the weaker hypothesis. (For $r=2$ this is clearly false, e.g., if $G$ is a matching.) Related notions of expansion (respectively stronger than and incomparable to ours) appear in \cite{krivelevich} and \cite{haber}. An additional application of Proposition~\ref{mainLemma}, given in Section~\ref{theorem Krivelevich Stopping}, is a short alternate proof of the following result of Krivelevich \cite{krivelevich}. \begin{theorem}\label{theorem Krivelevich Stopping} Let $\{\Aitch_{t}\}_{t\geq 0}$ denote the random $r$-graph process on $V$ in which each step adds an edge chosen uniformly from the current non-edges, let $T$ denote the first $t$ for which $\Aitch_{t}$ has no isolated vertices. Then $\Aitch_{T}$ has a perfect fractional matching w.h.p.. \end{theorem} \mn \textbf{Outline.} Section~\ref{sectionPrelims} includes definitions and brief linear programming background. Section~\ref{sectionGeneralHypergraph} treats $\complete{n}{r}$, proving Proposition~\ref{mainLemma} and Theorem~\ref{generalHypergraph}, and the corresponding results for $\mpart{n}{r}$ are proved in Section~\ref{sectionR-partite}. Finally, Section~\ref{sectionStopping} returns to $\complete{n}{r}$, using Proposition~\ref{mainLemma} to give an alternate proof of Theorem~\ref{theorem Krivelevich Stopping}. \section{Preliminaries}\label{sectionPrelims} Except where otherwise specified, $\h $ is an $r$-graph on $V=[n]$. As usual, we use $[t]$ for $\{1, 2, \ldots, t\}$ and $\lcho{X}{t}$ for the collection of $t$-element subsets of $X$. Throughout we use $\log$ for $\ln$ and take asymptotics as $n\ra \infty$ (with other parameters fixed), pretending (following a common abuse) that all large numbers are integers and assuming $n$ is large enough to support our arguments. \mn We need to recall a minimal amount of linear programming background (see e.g., \cite{schrijver1998} for a more serious discussion). For a hypergraph $\Aitch$, a \textit{fractional (vertex) cover} is a map $w : V \to [0,1]$ such that $\sum_{v \in e} w(v) \geq 1$ for all $e \in \Aitch$; the \textit{weight} of a cover $w$ is $|w| = \sum_{v} w(v)$; and the \emph{fractional cover number}, $\tau^*(\h)$, is the smallest such weight. Similarly a \textit{fractional matching} of $\h$ is a $\vp : \h \to [0,1]$ such that $\sum_{e \ni v} \vp (e) \leq 1$ for all $v \in V$; the weight of such a $\vp$ is defined as for fractional covers; and the \emph{fractional matching number}, $\nu^*(\h)$, is the \emph{maximum} weight of a fractional matching. In this context, LP-duality says that $\nu^{\ast}(\Aitch) = \tau^{\ast}(\Aitch)$ for any hypergraph. For $r$-graphs the common value is trivially at most $n/r$ (e.g., since $w\equiv 1/r$ is a fractional cover). A fractional matching in an $r$-graph is \emph{perfect} if it achieves this bound; that is, if $\sum\vp_e=n/r$ (equivalently $\sum_{e\ni v}\vp_e=1 ~\forall v$, which would be the definition of perfection in a nonuniform $\h$). \mn Finally, given $\h$ we say a nonempty $X\sub V$ is \emph{$\lambda$-expansive} if for all $Y\sub V\sm X$ of size at most $\lambda |X|$, there is some edge meeting $X$ but not $Y$. \section{Proofs of Proposition \ref{mainLemma} and Theorem \ref{generalHypergraph}}\label{sectionGeneralHypergraph} \begin{proof}[Proof of Proposition~\ref{mainLemma}] It is enough to show that if $w$ is a fractional cover with $t_0:= 1/r-\min_v w(v)>0$, then $|w|\geq n/r$, with the inequality strict if we assume the stronger version of \eqref{Y}. We give the argument under this stronger assumption; for the weaker, just replace the few strict inequalities below by nonstrict ones. Given $w$ as above, set, for each $t> 0$, \[ \mbox{$W_{t} = \{v \in [n] \ : \ w(v) \leq \frac{1}{r} - t\}$, $~~~W^{t} = \{v \in [n] \ : \ w(v) \geq \frac{1}{r} + t\}$.} \] Since $w$ is a fractional cover, each edge meeting $W_t$ must also meet $W^{t/(r-1)}$ (or the weight on the edge would be less than 1); so, since $W_t$ is independent, the hypothesis of Proposition~\ref{mainLemma} gives $|W^{t/(r-1)}| > (r-1) |W_t|$ for $t\in (0,t_0]$ (the $t$'s for which $W_t\neq \emptyset$). \mn For $\ft \in \mathbb{R}$, define $\fP(\ft) = |\{v \in [n] \ : \ w(v) \geq \ft\}|$. Then \begin{eqnarray*} \mbox{$\displaystyle \int_{0}^{1} \fP(\ft) \dd{\ft}$} &=& \mbox{$\displaystyle \int_{0} ^{1} \sum_{v \in [n]} \1_{\{w(v)\geq \ft\}}\dd{\ft}$}\\ &=& \mbox{$\displaystyle \sum_{v \in [n]} \int_{0} ^{1} \1_{\{w(v)\geq \ft\}} \dd{\ft} = \sum_{v \in [n]} w(v) = \tau^{\ast} ( \Aitch).$} \end{eqnarray*} We also have $|W^t| = \fP(1/r + t)$ and $|W_t| \geq n-\fP(1/r - t)$, implying \[ \fP(1/r + t/(r-1))\geq (r-1) (n-\fP(1/r -t)), \] with the inequality strict if $t\in (0,t_0]$. Thus, \begin{align*} \tau^{\ast} (\Aitch) &= \int_{0} ^{1} \fP(\ft) \dd{\ft} = \int_{0} ^{1/r} \fP(\ft) \dd{\ft} + \int_{1/r} ^{1} \fP(\ft) \dd{\ft}\\ &= \int_{0} ^{1/r} \fP(1/r - t) \dd{t} + \int_{0} ^{(r-1)^2 /r} \dfrac{\fP(1/r + t/(r-1))}{r-1} \dd{t}\\ &\geq \int_{0} ^{1/r} \left[\fP(1/r - t) + \dfrac{\fP(1/r + t/(r-1))}{r-1}\right] \dd{t}\\ &> \int_{0} ^{1/r} \left[\fP(1/r - t) + (r-1)\dfrac{n - \fP(1/r -t)}{r-1} \right]\dd{t} = \dfrac{n}{r}.\qedhere \end{align*} \end{proof} We should perhaps note that the converse of Proposition~\ref{mainLemma} is not true in general (failing, e.g., if $r>2$ and $\h$ is itself a perfect matching). But in the graphic case ($r=2$) the converse \emph{is} true (and trivial), and the proposition provides an alternate proof of the following characterization, which is \cite[Thm.\ 2.2.4]{scheinerman2011} (and is also contained in \cite[Thm.\ 2.1]{alon2007independent}, e.g.). \begin{corollary} A graph has a perfect fractional matching iff $|N(I)| \geq |I|$ for all independent $I$. \end{corollary} \nin (where $N(I) $ is the set of vertices with at least one neighbor in $I$). \begin{proof}[Proof of Theorem~\ref{generalHypergraph}] Given $r$, let (without trying to optimize) $k=(2r^2)^r$ and $c=k^{-1/r}=1/(2r^2)$, and let $\Aitch =\kout{\complete{n}{r}}{k}$. Theorem~\ref{generalHypergraph} (with this $k$) is an immediate consequence of Proposition~\ref{mainLemma} and the next two routine lemmas. (As usual $\alpha(\Aitch)$ is the size of a largest independent set in $\h$.) \end{proof} \begin{lemma}\label{outInd} W.h.p. $\alpha(\Aitch) < cn$. \end{lemma} \begin{lemma}\label{outExpand} W.h.p.\ every $X \subseteq V(\Aitch)$ with $|X| \leq c n$ is $(r-1)$-expansive. \end{lemma} \begin{proof}[Proof of Lemma~\ref{outInd}.] The probability that $S\in \C{[n]}{s}$ is independent in $\h$ is \[ \left[1 - \tfrac{(s-1)_{r-1}}{(n-1)_{r-1}}\right] ^{sk} < \exp\left[ - sk\left(\tfrac{s-r}{n} \right)^{r-1}\right]. \] (where $(a)_b = a(a-1)\cdots (a-b+1)$), and summing this over $S$ of size $cn$ bounds $\pr (\alpha \geq cn) $ by \[ 2^n \exp\left[ - cn k (c-r/n )^{r-1}\right] = \exp\left[n \left( \ln 2 - (1-o(1)) k c^r \right) \right], \] which tends to 0 as desired. \end{proof} \begin{proof}[Proof of Lemma~\ref{outExpand}.] For $X$, $Y$ disjoint subsets of $[n]$, let $B(X,Y)$ be the event that $Y$ meets all edges meeting $X$. Then, with $x=|X|$ and $y=|Y|$, \[ \pr (B(X,Y)) \leq \left[1-\tfrac{(n-y-1)_{r-1}}{(n-1)_{r-1}} \right]^{kx} \leq \left[1-\left(\tfrac{n-y-r}{n}\right)^{r-1} \right]^{kx} \leq \left[\tfrac{r(y+r)}{n} \right]^{kx}, \] the last inequality following from \beq{mx} 1-(1-x)^m \leq mx \enq (valid for $x\in [0,1] $ and nonnegative integer $m$). The probability that the conclusion of the lemma fails is thus less than \begin{eqnarray*} \mbox{$\displaystyle \sum \Cc{n}{rx} \Cc{rx}{x} \left[\tfrac{r(y+r)}{n} \right]^{kx}$} &< & \mbox{$\displaystyle \sum \left(\tfrac{ne}{rx} \right)^{rx} 2^{rx} \left[\tfrac{r(y+r)}{n} \right]^{kx}$}\\ &=& \mbox{$\displaystyle \sum\left[ (2e)^r \left(\tfrac{rx}{n} \right)^{k-r} ((r-1)+r/x)^k \right]^{x} $}\\ &< & \mbox{$\displaystyle \sum \left[ (4er)^r (r(2r-1)x/n)^{k-r} \right]^{x}$} ~=o(1), \end{eqnarray*} where the sums are over $1\leq x\leq cn$. \end{proof} \section{Proof of Theorem~\ref{r-partiteHypergraph}}\label{sectionR-partite} As in the proof of Theorem~\ref{generalHypergraph} we first show that the conclusions of Theorem~\ref{r-partiteHypergraph} are implied (deterministically) by sufficiently good expansion and then show that $\MPOut{n}{k}{r}$ w.h.p.\ expands as desired. We take $V = V_1 \cup \cdots \cup V_r$ to be our $r$-partition (so $|V_i|=n$\, $\forall i$) and below always assume $\h \sub \mpart{n}{r}$. \begin{proposition}\label{r-partite-expansion} Suppose $\eps\in (0,1/2)$ and $\lambda> 2r^3$ are fixed and $\Aitch $ satisfies: for any $i\in [r]$, $T\sub V_i$, $U_j\sub V_j$ for $j\neq i$ and $U=\cup_{j\neq i}U_j$, there is an edge meeting $T$ but not $U$ provided either \begin{itemize} \item[(i)] $|T| \leq \varepsilon n$ and $|U_j| \leq \lambda |T|$ $\forall j\neq i$, or \item[(ii)] $|T| \geq \eps n$ and $|U_j| \leq (1- \varepsilon) n$ $\forall j\neq i$. \end{itemize} Then $\Aitch$ admits a perfect fractional matching, and every minimum weight fractional cover of $\Aitch$ is constant on each $V_i$. \end{proposition} \begin{proof} Define a \textit{balanced assignment} to be a $w : V \to \mathbb{R}$ with $\sum_{v \in V_i} w(v) = 0$ and $w(e) \geq 0$ for all $e \in \Aitch$. We claim that (under our hypotheses) the only balanced assignment is the trivial $w \equiv 0$. To get Proposition \ref{r-partite-expansion} from this, let $f$ be a minimum weight fractional cover, and let $w_f (v) = f(v) - \sum_{u \in V_i} f(u) / n$, for each $i$ and $v \in V_i$. Then $w_f$ is a balanced assignment: $\sum_{v \in V_i} w_f (v) = 0$ is obvious and nonnegativity holds since $f(e) \geq 1$ and, by minimality, $\sum_{v \in V} f(v) \leq n $. Thus $w_f \equiv 0$, implying $f$ is as promised. \mn Suppose then that $w $ is a balanced assignment. For $X \subseteq V$ and $t \geq 0$, set $X^t = \{v \in X : w(v) \geq t\}$, $X_t = \{v \in X : w(v) < -t\}$, $X^{+} = X^0$ and $X^{-} = X_0$, and define the \textit{value} of $X$ to be $\psi (X) = \sum_{v \in X} |w(v)|$. Let $S=\{i\in [r]: |V_i ^{-}| \leq \varepsilon n\}$ and $B = [r] \setminus S$. \begin{lemma}\label{small sets have no value} If $X \subseteq V ^{-}$ and $|X| \leq \varepsilon n$, then $\psi (X) \leq r\psi (V^{+}) /\lambda$. \end{lemma} \begin{proof} For any $t > 0$, note that every edge meeting $X_{t}$ meets $V^{t/(r-1)}$ since otherwise, we could find an edge of negative weight. So since $|X_t| \leq |X| \leq \varepsilon n$, condition (i) implies $|V^{t/(r-1)}| \geq \lambda |X_t|$. Thus, \begin{align*} \psi (V^{+}) &= \int_{0} ^{\infty} |V^{u}| \dd{u} = \dfrac{1}{r-1}\int_{0} ^{\infty} |V^{t/(r-1)}| \dd{t}\\ &\geq \dfrac{\lambda}{r-1}\int_{0} ^{\infty} |X_{t}| \dd{t} = \dfrac{\lambda}{r-1} \psi (X).\qedhere \end{align*} \end{proof} \begin{lemma}\label{large sets have no value} If $|(V_i)_t| \geq \varepsilon n$, then $\max_{j\in S}| V_j^{t/(r-1)}|\geq (1-\eps)n$. \end{lemma} \begin{proof} Since any edge meeting $(V_i)_t$ meets $\cup_{j \neq i} V_{j} ^{t/(r-1)}$ and $|V_j ^{+}| \leq (1-\varepsilon)n$ for $j \in B$, there must (see (ii)) be some $j \in S$ with $|V_{j} ^{t/(r-1)}| \geq (1- \varepsilon)n$. \end{proof} We now claim $\psi (V_i) \leq 2r^2\psi (V)/\lambda$ for all $i$. For $i \in S$, we do a little better: Lemma~\ref{small sets have no value} gives $\psi (V_i ^{-}) \leq r\psi (V^{+}) / \lambda$, and balance (of $w$) then implies $\psi (V_i) =2\psi (V_i^{-}) \leq r\psi (V) / \lambda$. % For $i\in B$ write $W$ for $V_i$ (just to avoid some double subscripts) and set $T = \sup \{t \ : \ |W_t| \geq \varepsilon n\}$. Then \[ \psi (W^-) = \psi (W_T) + \psi (W^{-} \setminus W_T) \leq \psi (W_T) + T|W^{-} \setminus W_T|. \] Since $|W_T| < \varepsilon n$, Lemma~\ref{small sets have no value} gives $\psi (W_T) \leq r\psi (V^{+}) / \lambda$. On the other hand, $|W_t| \geq \varepsilon n$ for $t\in [0,T)$, with Lemma~\ref{large sets have no value}, implies that there is a $j\in S$ with $| V_j^{t/(r-1)}|\geq (1-\eps)n$ for all such $t$. Thus \begin{eqnarray*}\displaystyle \mbox{$(1-\eps)T|W^{-} \setminus W_T|$} &\leq& \mbox{$(1-\eps)nT ~\leq~ \int_{0}^{T} | V_{j} ^{t/(r-1)} | \dd{t} \leq \int_{0}^{\infty} | V_{j} ^{t/(r-1)} | \dd{t}$} \\ &=& \mbox{$(r-1)\psi ( V_{j} ^{+}) ~ \leq ~ r^2 \psi (V^{+})/\lambda.$} \end{eqnarray*} So, combining, we have $\psi (W) = 2\psi (W^{-}) \leq 2r^2\psi (V) / \lambda $ (establishing the claim) and \[ \mbox{$\psi (V) = \sum_{i} \psi (V_i) \leq 2r^3 \psi (V)/\lambda.$} \] But since $2r^3 < \lambda$, this forces $\psi (V) = 0$ and so $w \equiv 0$. \end{proof} \begin{proof}[Proof of Theorem \ref{r-partiteHypergraph}] Set $\gl = 4r^3$, $\eps = (2r\gl)^{-1}$ and $k =2r\eps^{-r}$ (so $k$ is a little more than $r^{4r}$). We show that w.h.p.\ $\Aitch = \MPOut{n}{k}{r}$ is as in Proposition~\ref{r-partite-expansion}. As earlier, let $B(X,Y)$ be the event that every edge meeting $X$ meets $Y$. \mn Suppose first that $T$ and $U$ are fixed with $|U_i| = \lambda |T| \leq \lambda \varepsilon n$. Then \[ \mbox{$\pr(B(T,U)) \leq \left[1 -\left(1-\frac{\lambda|T|}{n} \right)^{r-1} \right]^{k|T|} \leq \left( \frac{r\lambda|T|}{n} \right) ^{k|T|}.$} \] Summing over choices of $T$ and $U$ bounds the probability that $\Aitch$ violates the assumptions of the proposition for some $T$ and $U$ as in (i) by \begin{eqnarray*} \mbox{$r \sum_{t=1} ^{\varepsilon n} \Cc{n}{t} \Cc{n}{\lambda t} ^{r-1} \left(\frac{r \lambda t}{n} \right)^{kt}$} &\leq & \mbox{$r \sum_{t=1} ^{\varepsilon n} \left( \frac{en}{t}\right)^t \left( \frac{en}{\lambda t}\right)^{\lambda t(r-1)} \left(\frac{r \lambda t}{n} \right)^{kt}$}\\ &\leq& \mbox{$\sum_{t=1} ^{\varepsilon n} \left[ ( r \lambda t/n)^{k-r\lambda} \lambda (er)^{r\lambda} \right]^{t} = o(1).$} \end{eqnarray*} \mn Now say $T$ and $U$ are fixed with $|T| = \varepsilon n$ and $|U_i| = (1- \varepsilon)n$. Then \[ \pr(B(T,U)) \leq (1 - \eps^{r-1}) ^{k|T|} \leq \exp \left[- k|T|\varepsilon^{r-1} \right] \leq \exp \left[- kn \varepsilon^{r} \right]. \] So summing over possibilities for $(T,U)$ bounds the probability of a violation with $T$ and $U$ as in (ii) by \[ r 2^{nr} \exp \left[- kn \varepsilon^{r} \right] \leq \exp \left[n(r-k \varepsilon^r) \right] = o(1). \qedhere \] \end{proof} \section{Proof of Theorem \ref{theorem Krivelevich Stopping}}\label{sectionStopping} We now turn to our proof of Theorem~\ref{theorem Krivelevich Stopping}, for which we work with the following standard device for handling the process $\{\h_t\}$. \mn Let $\xi_S$, $S\in \lcho{[n]}{r}$, be independent random variables, each uniform from $[0,1]$, and for $\gl\in [0,1]$, let $G(\gl)$ be the $r$-graph on $[n]$ with edge set $\Ee(\gl) = \{ S \ : \ \xi_{S} \leq \gl \}$. Members of $\eee(\gl)$ will be called $\gl$-\emph{edges}. Note that with probability one, $G(0)$ is empty, $G(1)$ is complete, and the $\xi_S$'s are distinct. \mn Provided the $\xi_S$'s are distinct, this defines the discrete process $\{\h_t\}$ in the natural way, namely by adding edges $S$ in the order in which their associated $\xi_S$'s appear in $[0,1]$. We will work with the following quantities, where $\cc=\eps \log n$ for some small fixed (positive) $\eps$ and $g$ is a suitably slow $\go(1)$. \begin{itemize} \item $\gL =\min\{\gl: \mbox{$G(\gl)$ has no isolated vertices}\}$; \item $W_{\lambda} = \{v \in [n] \ : \ d_{G(\gl)} (v) \leq \cc \}$; \item $\gs = \frac{\log n - g(n)}{\Cc{n-1}{r-1}}$ and $\beta = \frac{\log n + g(n)}{\Cc{n-1}{r-1}}$; \item $N= \{v : \exists e \in \Ee(\beta),\ v \in e,\ e \cap W_{\gs} \neq \emptyset\}$ \end{itemize} (so $N$ is $W_{\gs}$ together with its $\Ee(\beta)$-neighbors). \bn \textbf{Preview.} With the above framework, our assignment is to show that $G(\gL)$ has a perfect matching w.h.p.. Perhaps the nicest part of this---and the point of coupling the different $G(\gl)$'s---is that, so long as $\gL\in [\gs,\gb]$, which we will show holds w.h.p., the desired assertion on $G(\gL)$ follows \emph{deterministically} from a few properties ((b)-(d) of Lemma~\ref{stoppingLemma}) involving $G(\gs)$, $G(\gb)$ \emph{or both}; so by showing that the latter properties hold w.h.p.\ we avoid the need for a union bound to cover possibilities for $\gL$. Production of the fractional matching is then similar to (though somewhat simpler than) what happens in \cite{krivelevich}: the relatively few vertices of $W_\gL$ (and some others) are covered by an (ordinary) matching, and the hypergraph induced by what's left has the expansion needed for Proposition~\ref{mainLemma}. \begin{lemma}\label{stoppingLemma} With the above setup (for fixed r) and $Z= n(\log n)^{-1/r}$, w.h.p. \begin{itemize} \item[(a)] $\gL\in [\gs, \beta]$; \item[(b)] $\ga(G(\gs))