Random greedy algorithm via branching process

Every edge ${\displaystyle E\in H}$ is independently and uniformly assigned a distinct real "birthtime" ${\displaystyle t_{E}\in [0,D]}$. The edges are taken one by one in the order of their birthtimes. The edge ${\displaystyle E}$ is accepted and included in ${\displaystyle P}$ if it does not overlap any previously accepted edges. Obviously, the subset ${\displaystyle P}$ is a packing and it can be shown that its size is ${\displaystyle |P|={\frac {n}{K+1}}}$ almost surely. To show that, let stop the process of adding new edges at time ${\displaystyle c}$. For an arbitrary ${\displaystyle \gamma >0}$, pick ${\displaystyle c,D_{0},\epsilon }$ such that for any ${\displaystyle (D_{0},\epsilon )}$-good hypergraph ${\displaystyle f_{x,H}(c)<\gamma ^{2}}$ where ${\displaystyle f_{x,H}(c)}$ denotes the probability of vertex ${\displaystyle x}$ survival (a vertex survives if it is not in any edges in ${\displaystyle P}$) until time ${\displaystyle c}$. Obviously, in such a situation the expected number of ${\displaystyle x}$ surviving at time ${\displaystyle c}$ is less than ${\displaystyle \gamma ^{2}n}$. As a result, the probability of ${\displaystyle x}$ surviving being less than ${\displaystyle \gamma n}$ is higher than ${\displaystyle 1-\gamma }$. In other words, ${\displaystyle P_{c}}$ must include at least ${\displaystyle (1-\gamma )n}$ vertices which means that ${\displaystyle |P|\geq (1-\gamma ){\frac {n}{K+1}}}$.

To complete the proof, it must be shown that ${\displaystyle \lim _{c\rightarrow \infty }\lim _{x,H}f_{x,H}(c)=0}$. For that, the asymptotic behavior of ${\displaystyle x}$ surviving is modeled by a continuous branching process. Fix ${\displaystyle c>0}$ and begin with Eve with the birthdate of ${\displaystyle c}$. Assume time goes backward so Eve gives birth in the interval of ${\displaystyle [0,c)}$ with a unit density Poisson distribution. The probability of Eve having ${\displaystyle k}$ birth is ${\displaystyle {\frac {e^{-c}c^{k}}{k!}}}$. By conditioning on ${\displaystyle k}$ the birthtimes ${\displaystyle x_{1},...,x_{k}}$ are independently and uniformly distributed on ${\displaystyle [0,c)}$. Every birth given by Eve consists of ${\displaystyle Q}$ offspring all with the same birth time say ${\displaystyle a}$. The process is iterated for each offspring. It can be shown that for all ${\displaystyle \epsilon >0}$ there exists a ${\displaystyle K}$ so that with a probability higher than ${\displaystyle (1-\epsilon )}$, Eve has at most ${\displaystyle K}$ descendants.

A rooted tree with the notions of parent, child, root, birthorder and wombmate shall be called a broodtree. Given a finite broodtree ${\displaystyle T}$ we say for each vertex that it survives or dies. A childless vertex survives. A vertex dies if and only if it has at least one brood all of whom survive. Let ${\displaystyle f(c)}$ denote the probability that Eve survives in the broodtree ${\displaystyle T}$ given by the above process. The objective is to show ${\displaystyle \lim _{c\rightarrow \infty }f(c)=0}$ and then for any fixed ${\displaystyle c}$, it can be shown that ${\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}$. These two relations complete our argument.

To show ${\displaystyle f(c)=0}$, let ${\displaystyle c\geq 0,\Delta c>0}$. For ${\displaystyle \Delta c}$ small, ${\displaystyle f(c+\Delta c)-f(c)\approx -(\Delta c)f(c)^{Q+1}}$ as, roughly, an Eve starting at time ${\displaystyle c+\Delta c}$ might have a birth in time interval ${\displaystyle [c,c+\Delta c)}$ all of whose children survive while Eve has no births in ${\displaystyle [0,c)}$ all of whose children survive. Letting ${\displaystyle \Delta c\rightarrow 0}$ yields the differential equation ${\displaystyle f'(c)=-f(c)^{Q+1}}$. The initial value ${\displaystyle f(0)=1}$ gives a unique solution ${\displaystyle f(c)=(1+Qc)^{-1/Q}}$. Note that indeed ${\displaystyle \lim _{c\rightarrow \infty }f(c)=0}$.

To prove ${\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}$, consider a procedure we call History which either aborts or produces a broodtree. History contains a set ${\displaystyle T}$ of vertices, initially ${\displaystyle T=\{x\}}$. ${\displaystyle T}$ will have a broodtree structure with ${\displaystyle x}$ the root. The ${\displaystyle y\in T}$ are either processed or unprocessed, ${\displaystyle x}$ is initially unprocessed. To each ${\displaystyle y\in T}$ is assigned a birthtime ${\displaystyle t_{y}}$, we initialize ${\displaystyle t_{x}=c}$. History is to take an unprocessed ${\displaystyle y\in T}$ and process it as follows. For the value of all ${\displaystyle t_{E}}$ with ${\displaystyle y\in E}$ but with no ${\displaystyle x\in E}$ that has already been processed, if either some ${\displaystyle E}$ has ${\displaystyle t_{E}<t_{y}}$ and ${\displaystyle y,z\in E}$ with ${\displaystyle z\in T}$ or some ${\displaystyle E,E'}$ have ${\displaystyle t_{E},t_{E'}<t_{y}}$ with ${\displaystyle y\in E,E'}$ and ${\displaystyle |E\cup E'|>1}$, then History is aborted. Otherwise for each ${\displaystyle E}$ with ${\displaystyle t_{E}<t_{y}}$ add all ${\displaystyle z\in E-\{y\}}$ to ${\displaystyle T}$ as wombmates with parent ${\displaystyle y}$ and common birthdate ${\displaystyle t_{E}}$. Now ${\displaystyle y}$ is considered processed. History halts, if not aborted, when all ${\displaystyle y\in T}$ are processed. If History does not abort then root ${\displaystyle x}$ survives broodtree ${\displaystyle T}$ if and only if ${\displaystyle x}$ survives at time ${\displaystyle c}$. For a fixed broodtree, let ${\displaystyle f(T,c)}$ denote the probability that the branching process yields broodtree ${\displaystyle T}$. Then the probability that History does not abort is ${\displaystyle f(T,c)}$. By the finiteness of the branching process, ${\displaystyle \sum f(T,c)=1}$, the summation over all broodtrees ${\displaystyle T}$ and History does not abort. The ${\displaystyle lim^{*}}$ distribution of its broodtree approaches the branching process distribution. Thus ${\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}$.