# The Linear $q$-Hypergraph Process

Sayok Chakravarty  Nicholas Spanier

Abstract

We analyze a random greedy process to construct $q$-uniform linear hypergraphs
using the differential equation method. We show for $q=o(\sqrt{\log n})$, that
this process yields a hypergraph with $\frac{n(n-1)}{q(q-1)}(1-o(1))$ edges.
We also give some bounds for maximal linear hypergraphs.

##  1 Introduction

###  1.1 $F$-free processes and the Differential Equation Method

The differential equation method for graph processes was popularized by
Wormald in 1999 [13] to analyze random graph processes. Random graph processes
have been well studied in various contexts [6, 12, 7, 1, 2, 10]. The survey
[3] provides an accessible introduction to the differential equation method. A
common application of the differential method is the analysis of the
$\cal{F}$-free process where $\cal{F}$ is a family of graphs. This is random
process which creates a graph $G_{i}$ on $n$ vertices by adding edges
uniformly at random one at a time so $G_{i}$ contains no subgraph in the
family $\cal{F}$. The case in which $\mathcal{F}$ is a single graph has been
studied for graphs including $K_{3}$ and $K_{4}$ to give lower bounds on the
Ramsey numbers $r(3,t)$ and $r(4,t)$ [4, 8, 11].

This paper uses the differential equation method to construct approximate
partial Steiner systems. An $(n,q,t)$ partial Steiner system is a family
$\mathcal{H}\subset\binom{[n]}{q}$ so that any $t$ subset is contained in at
most one element of $\mathcal{H}$. It is easy to see that
$|\mathcal{H}|\leq\frac{\binom{n}{t}}{\binom{q}{t}}$. When
$|\mathcal{H}|=\frac{\binom{n}{t}}{\binom{q}{t}}(1-o(1))$ as
$n\rightarrow\infty$ we say $\mathcal{H}$ is an approximate Steiner system.
Theorem 7.1 of [13] uses the differential equation method to show that a
greedy matching of a $k$-uniform hypergraph will use almost all of the
vertices given certain degree conditions are satisfied. The problem of finding
an $(n,q,t)$ partial Steiner system on $[n]$ can be viewed as finding a
matching in a particular $k$-uniform hypergraph. In [13], Wormald analyzes the
greedy packing process to construct a hypergraph matching. He comments that
while the proof only works for fixed $k$, one should be able to allow $k$ to
grow as a function of the number of vertices and get an analogous result.
Wormald’s result suggests the greedy packing process could construct a
$(n,q,2)$ approximate partial Steiner system for $q=o(\sqrt[4]{\log n})$. We
explain the connection between Wormald’s result and our result in Section 1.2.
Our main contribution is that we show that an $\mathcal{F}$-free process
constructs an $(n,q,2)$ approximate partial Steiner system for $q=o(\sqrt{\log
n)}$.

Bohman and Warnke showed there exists approximate partial Steiner triple
systems with high girth by analyzing an $F$-free process [5]. Our work uses
their approach to analyze the process of $q$-uniform graphs where $q$ may
depend on $n$.

###  1.2 $q$-Linear Process

A hypergraph $\mathcal{H}$ is called linear if for any $A,B\in E(\mathcal{H})$
we have $|A\cap B|\leq 1$. In other words, any pair of vertices appears in at
most one edge. Suppose that $\mathcal{H}$ is $q$-uniform. Then
$|E(\mathcal{H})|\leq\frac{\binom{n}{2}}{\binom{q}{2}}=\frac{n(n-1)}{q(q-1)}$
as the $\binom{q}{2}$ pairs in each edge are distinct.

Consider the following simple randomized greedy algorithm for constructing a
maximal $q$-uniform linear hypergraph where we add one edge at each step. Let
$\mathcal{H}_{i}$ be the hypergraph at step $i$ and let $e_{i}$ be the edge
added at step $i$

1\. Let $\mathcal{H}_{0}$ be the empty $q$-uniform hypergraph on $[n]$.

2\. For $i\geq 1$, at step $i$ pick $e_{i}$ uniformly at random from the set

$\left\\{e\in\binom{[n]}{q}:|e\cap e_{j}|\leq 1\text{ for }1\leq j\leq
i-1\right\\}$

and form $\mathcal{H}_{i}$ by adding $e_{i}$ to $\mathcal{H}_{i-1}$.

We call this the $q$-linear process. We analyze the stopping time of this
algorithm for various values of $q$ that may depend on $n$. Our first result
gives a lower bound on sizes of maximal linear hypergraphs. Note that such
lower bounds give a lower bound on the stopping time of the $q$-linear
process.

######  Proposition 1.

Let $\mathcal{H}$ be a $q$-uniform linear hypergraph on $[n]$ that is maximal
(i.e. no edge can be added to $\mathcal{H}$ while maintaining linearity). Then
$e(\mathcal{H})\geq\frac{n(n-q+1)}{q(q-1)^{2}}=\frac{n^{2}}{q^{3}}(1-o(1))$.

Observe that Proposition 1 shows that any maximal partial $(n,q,2)$ Steiner
system has at least $\frac{n^{2}}{q^{3}}$ edges. In particular the $q$-linear
process must continue for at least $\frac{n^{2}}{q^{3}}$ steps.

In addition to Proposition 1, notice that there is a trivial lower bound for
the size of a maximal $(n,q,2)$ partial Steiner system of $\frac{n}{q}$ by a
counting argument. Notice that since $\frac{n}{q}>\frac{n^{2}}{q^{3}}$ when
$q>\sqrt{n}$ then once $q>\sqrt{n}$ the trivial lower bound is better than the
bound from Proposition 1. Furthermore, when the trivial lower bound is better
than the bound from Proposition 1, Proposition 2 says exactly how long the
process continues asymptotically.

######  Proposition 2.

Let $\mathcal{H}$ be a $q$-uniform linear hypergraph on $[n]$ with
$q\geq\sqrt{2n}$. Then $e(\mathcal{H})<q$. Further, if $\mathcal{H}$ is
maximal then $e(\mathcal{H})=\Theta(\frac{n}{q})$.

The problem of finding an $(n,q,t)$ partial Steiner system on $[n]$ can be
viewed as finding a matching in a $\binom{q}{t}$-uniform hypergraph $H$ where
$V(H)=\binom{[n]}{t}$ and for each $S\in\binom{[n]}{q}$ $H$ has an edge which
corresponds to all of the $t$-sets in $S$. In [13] Wormald defines the greedy
packing process on a hypergraph $H$ as the process which picks an edge from
$H$ one at a time uniformly at random and then deletes all the vertices in the
chosen edge and continues until there are no edges remaining. We state
Wormald’s result below:

######  Theorem 3.

Let $H$ be a $k$-uniform hypergraph with $\nu$ vertices where $k$ is a fixed
constant. Assume $\nu<r^{C}$ for some constant $C,\delta=o(r^{1/3})$ and
$r=o(\nu)$. Also if $d(v)$ is the degree of vertex $v$ in $H$ then assume
$|d(v)-r|\leq\delta$. Then for any $\epsilon_{0}<\frac{1}{9k(k-1)+3}$ a.a.s.
at most $\frac{v}{r^{\epsilon_{0}}}$ vertices remain at the end of the greedy
packing process applied to $H$.

Based on the connection between partial Steiner systems on $[n]$ and matchings
in the hypergraph $H$, the number of unused vertices in the greedy packing
process is the number of unused pairs at the end of the $q$-linear process.
Note that the correspondences between the greedy packing process and the
$q$-linear process is given by $\nu=\binom{n}{2}$ and $k=\binom{q}{2}$. Hence,
for the partial Steiner system to have $(1-o(1))\frac{n(n-1)}{q(q-1)}$ edges,
Wormald’s result suggests that if $k$ were allowed to grow as a function of
$\nu$ then we would need that $\frac{\nu}{r^{\epsilon_{0}}}=o(n^{2})$.Then
using the fact that $r=o(\nu)=o(n^{2})$ and
$\epsilon_{0}=O(\frac{1}{k^{2}})=O(\frac{1}{q^{4}})$, we would need that
$q=o(\sqrt[4]{\log n})$.

Our main result allows us to still get almost all of the edges until $q$ is
$o(\sqrt{\log n})$, giving an improvement over the expected result from
Wormald 1999 [13].

######  Theorem 4.

Let $q=o(\sqrt{\ln n})$ and let $\mathcal{H}$ be a $q$-uniform hypergraph on
$[n]$ obtained from the $q$-linear process. Then whp
$|E(\mathcal{H})|\geq\frac{n(n-1)}{q(q-1)}(1-o(1))$.

Note that for $q$ between $\sqrt{\log n}$ and $\sqrt{2n}$ all we know about
the $q$-linear process is the lower bound from Proposition 1.

In Section 2 of this paper, we will prove Proposition 1 and Proposition 2 and
in Section 3 we will prove Theorem 4. Throughout this paper, we will use the
notation $f(n)\ll g(n)$ to mean $f(n)=o(g(n))$.

##  2 Auxiliary Results

We will begin by proving Proposition 1

###### Proof.

Let $\mathcal{H}$ be a $q$-uniform linear hypergraph on $[n]$ that is maximal.
Consider the graph $G$ on $[n]$ whose edge set is pairs that are not present
in any edge of $\mathcal{H}$. Then $G$ is $K_{q}$-free as a $K_{q}$ in $G$
corresponds to an edge that can be added to $\mathcal{H}$. Then
$\binom{n}{2}=e(\mathcal{H})\binom{q}{2}+e(G)$. Hence, by Turan’s theorem

$\displaystyle e(\mathcal{H})$
$\displaystyle=\binom{q}{2}^{-1}\left(\binom{n}{2}-e(G)\right)$
$\displaystyle\geq\binom{q}{2}^{-1}\left(\binom{n}{2}-\left(1-\frac{1}{q-1}\right)\frac{n^{2}}{2}\right)$
$\displaystyle=\frac{n(n-q+1)}{q(q-1)^{2}}$

Next, we prove Proposition 2.

###### Proof.

Let $\mathcal{H}$ be a $q$-uniform linear hypergraph on $[n]$. Let
$e(\mathcal{H})=m$ and let $E(\mathcal{H})=\\{e_{i}:i\in[m]\\}$. Now define
$\mathcal{H}_{i}$ as the $q$-uniform hypergraph on $[n]$ with
$E(\mathcal{H}_{i})=\\{e_{j}:j\in[i]\\}$. Define
$V_{i}=[n]\setminus\cup_{j=1}^{i}e_{j}$ be the set of vertices not used by any
edge in $\mathcal{H}_{i}$. Now notice that since $\mathcal{H}$ is linear,
$|e_{i+1}\cap\cup_{j=1}^{i}e_{j}|\leq i$, so $|V_{i}\setminus V_{i+1}|\geq
q-i$. Now let $V_{0}=[n]$ and notice that $\forall i\in[m]$

$\displaystyle|V_{i}|$ $\displaystyle=n-\sum_{j=1}^{i}|V_{j-1}\setminus
V_{j}|$ $\displaystyle\leq n-\sum_{j=1}^{i}q-(j-1)$
$\displaystyle=n-iq+\frac{1}{2}i(i-1)$

Now let $f(x)=n-qx+\frac{1}{2}x(x-1)$ and notice that $f(i)\geq|V_{i}|$ for
all $i\in[m]$. Also, notice that $|V_{i}|$ is a non-negative integer for all
$i\in[m]$ since it is the number of vertices not used in any edge of
$\mathcal{H}_{i}$. Then notice that $f(q)=n-\frac{1}{2}q^{2}-\frac{1}{2}q<0$
since $q\geq\sqrt{2n}$, so if $m\geq q$ this would lead to a contradiction
since $|V_{q}|\leq f(q)<0$ but $|V_{q}|\geq 0$. Thus $m<q$.
Now notice that $\sum_{i=1}^{m}|V_{i-1}\backslash
V_{i}|\geq\sum_{i=1}^{m}(q-(i-1))=mq-\frac{1}{2}m(m-1)$ and further,
$\sum_{i=1}^{m}|V_{i-1}\backslash V_{i}|\leq n$. Thus we get that
$m(q-\frac{1}{2}(m-1))\leq n$ but since $m-1<q$ then $m(q-\frac{1}{2}q)\leq
n$. Thus $m\leq\frac{2n}{q}$ so $m=O(\frac{n}{q})$.
Next, assume $\mathcal{H}_{i}$ is maximal and notice that every new edge uses
at most $q$ vertices not used by other edges, and there cannot be $q$ unused
vertices because $\mathcal{H}$ is maximal. Thus
$m>\frac{n-q}{q}=\Omega(\frac{n}{q})$. Thus
$e(\mathcal{H})=\Theta(\frac{n}{q})$.

##  3 Analysis of the $q$-Linear Process

We prove Theorem 4 using the differential equation method.

###  3.1 Trajectories and Definitions

To understand $q$-linear process we need to track the codegree of sets
$A\subset[n]$. The codegree of $A$ at step $i$ is the number of $B\subset[n]$
with $A\cap B=\emptyset$ so that $A\cup B$ can be added to
$\mathcal{H}_{i-1}$. Towards this end, for each $J\subset[n]$ with
$|J|=j\in\\{0\\}\cup[q-1]$ consider the sets:

$\displaystyle H(i):=\left\\{e\in\binom{[n]}{q}:|e\cap e_{k}|\leq 1\text{ for
}1\leq k\leq i-1\right\\}$ $\displaystyle P_{j}(i):=\left\\{J\in{[n]\choose
j}:J\subset e\text{ for some }e\in H(i)\right\\}$ $\displaystyle
Y_{J}(i):=\begin{cases}\left\\{K\in{[n]\setminus J\choose q-j}:J\cup K\in
H(i)\right\\}&J\in P_{j}(i+1)\\\ Y_{J}(i-1)&J\not\in P_{j}(i+1)\end{cases}$

Here $P_{j}(i)$ represents $j$ sets which can still be a subset of a new edge
at step $i$, and $Y_{J}(i)$ represents the codegree of a set in $P_{j}(i)$
with the convention that if $J\not\in P_{j}(i)$ then we freeze $Y_{J}$ at its
current value. We are particularly interested in $Y_{\emptyset}(i)$ as this
gives the number of available edges at step $i$, and we give this set another
name $H(i)$ for clarity.

Next we will define trajectory functions which we expect the random variables
$|Y_{J}(i)|$ to follow. Observe that after $i$ steps the proportion of pairs
that are not in any edge is
$\frac{\binom{n}{2}-i\binom{q}{2}}{\binom{n}{2}}=1-\frac{iq(q-1)}{n(n-1)}$.
Our heuristic is that the probability that a pair is not in any edge at step
$i$ is $1-\frac{iq(q-1)}{n(n-1)}$ and the events that distinct pairs are not
in any edges are mutually independent. Now we will define a continuous time
variable $t$ which relates to discrete steps by $t(i)=t_{i}=\frac{i}{n(n-1)}$
and define the following functions:

$\displaystyle p(t):=1-q(q-1)t$ $\displaystyle y_{j}(t):={n-j\choose
q-j}p^{{q\choose 2}-{j\choose 2}}\forall j\in[q-1]\cup\\{0\\}$ $\displaystyle
h(t):={n\choose q}p^{{q\choose 2}}$

Notice that $p$ is a continuous valued function which matches are heuristic
for the probability that a pair is not in an edge together at step $i$ when
$t=\frac{i}{n(n-1)}$. Further, notice that if our heuristic is close to true,
then $y_{j}(t)$ gives the approximate size of $Y_{J}(i)$ when
$t=\frac{i}{n(n-1)}$ given that $J\in P_{j}$. Also note that $h(t)=y_{0}(t)$.

Now with these trajectories functions, we define our targeted stopping time
$m_{0}$ and the error we allowed on the trajectories $\epsilon_{j}$ as
follows:

$\displaystyle f:=(\log\log n)^{2}$ $\displaystyle\beta:=\frac{1}{6q^{2}}$
$\displaystyle m_{0}:=\lfloor\frac{n(n-1)}{q(q-1)}(1-n^{-\beta})\rfloor$
$\displaystyle\epsilon_{j}:={n-j\choose q-j}n^{-1+3\beta{q\choose
2}}q^{f}p^{-{j\choose 2}-2{q\choose 2}}$
$\displaystyle\epsilon_{H}:=\epsilon_{0}$

Now to prove Theorem 4, we prove the following lemma:

######  Lemma 5.

For all $0\leq i\leq m_{0}$, and for all $j\in[q-1]\cup\\{0\\}$ we have that

$\displaystyle\left||H(i)|-h(t_{i})\right|\leq\epsilon_{H}$
$\displaystyle||Y_{J}(i)|-y_{j}(t_{i})|\leq\epsilon_{j}\forall J\in P_{j}(i)$

whp

Now notice that if $\epsilon_{H}(t)=o(h(t))$ and
$\epsilon_{j}(t)=o(y_{j}(t))$, this will show that whp $H\sim h$ and
$Y_{J}\sim y_{j}$, which since $h(t_{m_{0}})\gg 1$ this will prove Theorem 4.
Let $\mathcal{G}_{i}$ be the event that all the estimates in Lemma 5 hold for
all $j\leq i$.

To see that $\epsilon_{j}(t)=o(y_{j}(t))$ for all $j\in[q-1]\cup\\{0\\}$
notice that for all $t\in[0,\frac{m_{0}}{n(n-1)}]$

$\displaystyle\frac{\epsilon_{j}(t)}{y_{j}(t)}$
$\displaystyle=\frac{{n-j\choose q-j}n^{-1+3\beta{q\choose
2}}q^{f}p^{-{j\choose 2}-2{q\choose 2}}}{{n-j\choose q-j}p^{{q\choose
2}-{j\choose 2}}}$ $\displaystyle=q^{f}n^{-1+3\beta{q\choose 2}}p^{-3{q\choose
2}}$ $\displaystyle\leq q^{f}n^{-1+6\beta{q\choose 2}}=o(1)$

Where last statement in the above follows from our choices of $f$ and $\beta$.
Notice that since we want $n^{-\beta}=o(1)$ then we need
$\beta=\omega(\frac{1}{\log n})$, and we also need
$\beta=\Theta(\frac{1}{{q\choose 2}})$. Thus we need that ${q\choose 2}=o(\log
n)$ which holds since we assumed $q=o(\sqrt{\log n})$.

To prove Lemma 5, we will define the following random variable where
$J\in{[n]\choose j}$ for $j\in[q-1]\cup\\{0\\}$:

$\displaystyle
Y_{J}^{\pm}(i)=\begin{cases}|Y_{J}(i)|-(y_{j}(t_{i})\pm\epsilon_{j})&\mathcal{G}_{i-1}\text{
holds}\\\ Y_{J}^{\pm}(i-1)&\text{otherwise}\end{cases}$

###  3.2 Expected One-Step Change of $Y_{J}$

Let $\Delta Y_{J}(i)=|Y_{J}(i+1)|-|Y_{J}(i)|$ and let $\mathcal{F}_{i}$ be the
natural filtration of the process at step $i$. We refer to $\Delta Y_{J}(i)$
as the one step change of $Y_{J}(i)$.

We now show that

$\mathbb{E}[\Delta Y_{J}(i)|\mathcal{F}_{i}]=-\frac{1}{|H(i)|}\left(\sum_{K\in
Y_{J}(i)}\left(\sum_{S\subset J,\,T\subset K,\,|S|+|T|\geq 2,\,|T|\geq
1}(-1)^{|S|+|T|}(|S|+|T|-1)|Y_{S\cup T}(i)|\right)\right)$

Observe that $\Delta Y_{J}(i)$ is the number of elements in the codegree of
$Y_{J}(i)$ that are made unavailable by the addition of $e_{i}$ to
$\mathcal{H}_{i-1}$. We show that for fixed $K\in Y_{J}(i)$ the number of
edges $e_{i}$ that causes $K\notin Y_{J}(i+1)$ is

$\sum_{S\subset J,\,T\subset K,\,|S|+|T|\geq 2,\,|T|\geq
1}(-1)^{|S|+|T|}(|S|+|T|-1)|Y_{S\cup T}(i)|$

Suppose $e\in H(i)$ is such that $|e\cap J|=k$ and $|e\cap K|=\ell$ such that
$k+\ell\geq 2$. We show that if $k=0,1$ then $e$ is counted once in the sum
and that if $k\geq 2$ then $e$ is counted 0 times in the sum.

Let $k=0$. Then $e$ is counted

$\sum_{m=2}^{\ell}\binom{\ell}{m}(-1)^{m}(m-1)=1$

times.

Let $k=1$. Then $e$ is counted

$\sum_{m=2}^{\ell}\binom{\ell}{m}(-1)^{m}(m-1)+\sum_{m=1}^{\ell}\binom{\ell}{m}(-1)^{m+1}m=1$

times.

Let $k\geq 2$. Then $e$ is counted

$\sum_{0\leq m_{1}\leq k,1\leq m_{2}\leq\ell,m_{1}+m_{2}\geq
2}\binom{k}{m_{1}}\binom{\ell}{m_{2}}(-1)^{m_{1}+m_{2}}(m_{1}+m_{2}-1)=0$

times.

We leave the proof of the combinatorial identities used above for the
appendix.

###  3.3 Supermartingale and Submartingale Properties

We now show that $\Delta Y_{J}^{+}(i)$ is a supermartingale. We first note
that

$\Delta
Y_{J}^{+}(i)=\left(Y_{J}(i+1)-Y_{J}(i)\right)-(y_{j}(t_{i+1})-y_{j}(t_{i}))-(\epsilon_{j}(t_{i+1})-\epsilon_{j}(t_{i}))$

Since by Taylor’s theorem

$y_{j}(t_{i+1})-y_{j}(t_{i})=\frac{y_{j}^{\prime}(t_{i})}{n(n-1)}+\frac{1}{2}\frac{y_{j}^{\prime\prime}(c)}{n^{2}(n-1)^{2}}$

for some $c\in[t_{i},t_{i+1}]$, and similarly

$\epsilon_{j}(t_{i+1})-\epsilon_{j}(t_{i})=\frac{\epsilon_{j}^{\prime}(t_{i})}{n(n-1)}+\frac{1}{2}\frac{\epsilon_{j}^{\prime\prime}(c)}{n^{2}(n-1)^{2}}$

for some $c\in[t_{i},t_{i+1}]$, then we have

$\displaystyle\mathbb{E}[\Delta Y_{J}^{+}(i)|\mathcal{F}_{i}]$
$\displaystyle\leq\mathbb{E}[\Delta
Y_{J}(i)|\mathcal{F}_{i}]-\frac{y_{j}^{\prime}(t_{i})}{n(n-1)}-\frac{\epsilon_{j}^{\prime}(t_{i})}{n(n-1)}+\frac{\sup_{s\in[0,\frac{m_{0}}{n(n-1)}]}|y_{j}^{\prime\prime}(s)|}{2n^{2}(n-1)^{2}}+\frac{\sup_{s\in[0,\frac{m_{0}}{n(n-1)}]}|\epsilon_{j}^{\prime\prime}(s)|}{2n^{2}(n-1)^{2}}\,\,\,(1)$

Note that in the event $\mathcal{G}_{i-1}$

$\displaystyle\mathbb{E}[\Delta Y_{J}(i)|\mathcal{F}_{i}]$
$\displaystyle\leq\frac{y_{j}(t_{i})+\epsilon_{j}(t_{i})}{h(t_{i})-\epsilon_{h}(t_{i})}\sum_{m=2}^{q}\left(\binom{q}{m}-\binom{j}{m}\right)(m-1)((-1)^{m+1}y_{m}(t_{i})+\epsilon_{m}(t_{i}))$
$\displaystyle\sim\sum_{m=2}^{q}\left(\binom{q}{m}-\binom{j}{m}\right)(m-1)\left((-1)^{m+1}\frac{y_{j}y_{m}}{h}+\frac{y_{j}\epsilon_{m}}{h}\right)$

To show that $\left\\{Y_{J}^{+}(i)\right\\}$ is a supermartingale, we need to
verify that $\mathbb{E}[\Delta Y_{J}^{+}(i)|\mathcal{F}_{i}]\leq 0$. We do
this by showing that the negative terms in (1) are larger than the positive
terms. We do this by showing the following:

######  Lemma 6.

The following hold

$({q\choose 2}-{j\choose
2})\frac{y_{j}y_{2}}{h}=\frac{y_{j}^{\prime}}{n(n-1)}$
$\binom{q}{2}\frac{y_{j}\epsilon_{2}}{h}\leq\frac{1}{2}\frac{\epsilon_{j}^{\prime}}{n(n-1)}$
$\binom{q}{m}\frac{y_{j}y_{m}}{h}\ll\frac{1}{q}\frac{\epsilon_{j}^{\prime}}{n(n-1)}\text{
for }m\geq 3$
$\binom{q}{m}\frac{y_{j}\epsilon_{m}}{h}\ll\frac{1}{q}\frac{\epsilon_{j}^{\prime}}{n(n-1)}\text{
for }m\geq 3$
$\frac{\sup_{s\in[0,\frac{m_{0}}{n(n-1)}]}|y_{j}^{\prime\prime}(s)|}{2n^{2}(n-1)^{2}}+\frac{\sup_{s\in[0,\frac{m_{0}}{n(n-1)}]}|\epsilon_{j}^{\prime\prime}(s)|}{2n^{2}(n-1)^{2}}\ll\frac{\epsilon_{j}^{\prime}}{n(n-1)}$

We leave the proofs of these statements for the appendix.

###  3.4 Absolute Bound on One-Step Change

We will now give an absolute bound on the one step change of $Y_{J}^{+}$.
First, notice that

$\displaystyle|\Delta Y_{J}^{+}(i)|\leq|\Delta
Y_{J}(i)|+\sup_{t\in[t_{i},t_{i+1}]}\frac{|y_{j}^{\prime}(t)|}{n(n-1)}+\sup_{t\in[t_{i},t_{i+1}]}\frac{|\epsilon_{j}^{\prime}(t)|}{n(n-1)}$

We will start by bounding $\Delta|Y_{J}(i)|$. Notice that since $Y_{J}$ only
changes when an available edge containing $J$ becomes unavailable, then
existing edges can only cause the absolute change in $Y_{J}(i)$ to be smaller
since sets that would have been removed from the codegree of $J$ were already
not in the codegree of $J$. Thus WLOG we may assume $i=0$, and now we will
consider three types of edges, $e$, which can be added, edges where $|e\cap
J|\geq 2$, edges where $|e\cap J|=1$, and edges where $|e\cap J|=0$. First,
since we freeze $Y_{J}$ once $J$ has an intersection with an existing edge of
size at least 2, in the case where $|e\cap J|\geq 2$ we get that $\Delta
Y_{J}(0)=0$. Next, when $|e\cap J|=1$ we get the following:

$\displaystyle|\Delta Y_{J}(0)|$ $\displaystyle\leq{q-1\choose 1}{n-j\choose
q-j-1}$

Now to show this bound on $|\Delta Y_{J}(0)|$ when $|e\cap J|=1$ is larger
than our bound when $|e\cap J|=0$, and also to show that this bound is the
largest term in the bound for $Y_{J}^{+}(i)$, we will give a lower bound on
the quantity $(q-1){n-j\choose q-j-1}$.

$\displaystyle(q-1){n-j\choose q-j-1}$
$\displaystyle\geq(q-1)(\frac{n-j}{q-j-1})^{q-j-1}$
$\displaystyle=\Omega(n^{q-j-1}q^{-q+j+2})$

Next, when $|e\cap J|=0$ we get the following:

$\displaystyle|\Delta Y_{J}(0)|$ $\displaystyle\leq{q\choose 2}{n-j\choose
q-j-2}$ $\displaystyle\leq\frac{1}{2}q^{2}(\frac{(n-j)e}{q-j-2})^{q-j-2}$
$\displaystyle=O(n^{q-j-2}e^{q-j-2}q^{2})$
$\displaystyle=o(n^{q-j-1}q^{-q+j+2})$

Thus for all $J$ and for all $i$ we have that $|\Delta
Y_{J}(i)|\leq(q-1)\binom{n-j}{q-j-1}$

Next, we will bound
$\sup_{t\in[t_{i},t_{i+1}]}\frac{|y_{j}^{\prime}(t)|}{n(n-1)}$. Notice that
for all $t\in[0,m_{0}]$

$\displaystyle\left|\frac{y_{j}^{\prime}(t)}{n(n-1)}\right|$
$\displaystyle=\left|\frac{{n-j\choose q-j}p^{{q\choose 2}-{j\choose
2}-1}({q\choose 2}-{j\choose 2})(-q(q-1))}{n(n-1)}\right|$
$\displaystyle=O((\frac{ne}{q-j})^{q-j}q^{4}n^{-2})$
$\displaystyle=O(n^{q-j-2}q^{4}e^{q-j})$
$\displaystyle=o(n^{q-j-1}q^{-q+j+2})$

Finally we will bound
$\sup_{t\in[t_{i},t_{i+1}]}\frac{|\epsilon_{j}^{\prime}(t)|}{n(n-1)}$. Now
notice that for all $t\in[0,m_{0}]$ we get that

$\displaystyle\left|\frac{\epsilon_{j}^{\prime}(t)}{n(n-1)}\right|$
$\displaystyle=\left|\frac{{n-j\choose q-j}n^{-1+3\beta{q\choose
2}}q^{f}p^{-{j\choose 2}-2{q\choose 2}-1}(-{j\choose 2}-2{q\choose
2})(-q(q-1))}{n(n-1)}\right|$
$\displaystyle=O((\frac{ne}{q-j})^{q-j}n^{-1+3\beta{q\choose
2}}q^{f}(1-q(q-1)\frac{m_{0}}{n(n-1)})^{-{j\choose 2}-2{q\choose
2}-1}n^{-2}q^{4})$ $\displaystyle=O(n^{q-j-3+3\beta{q\choose
2}+\beta({j\choose 2}+2{q\choose 2}+1)}q^{4+f}e^{q-j})$
$\displaystyle=o(n^{q-j-1}q^{-q+j+2})$

Thus $|\Delta Y_{J}(i)|\leq(q-1){n-j\choose q-j-1}$ for all $J$ and $i$.

###  3.5 Freedman Inequality

To finish the proof of Lemma 5 we use Freedman’s Inequality which we state
below [9].

######  Theorem 7.

Let $\left\\{S(i)\right\\}_{i\geq 0}$ be a supermartingale with respect to the
filtration $\mathcal{F}=\left\\{\mathcal{F}_{i}\right\\}_{i\geq 0}$. Writing
$\Delta S(i)=S(i+1)-S(i)$, suppose that $\max_{i\geq 0}|\Delta S(i)|\leq C$
and $\sum_{i\geq 0}\mathbb{E}(|\Delta S(i)|\,|\,\mathcal{F}_{i})\leq V$. Then,
for any $z>0$

$\mathbb{P}\left(S(i)\geq S(0)+z\text{ for some }i\geq
0\right)\leq\exp\left\\{-\frac{z^{2}}{2C(V+z)}\right\\}$

Observe that if we set $S=Y_{J}^{+}$ and $z=-Y_{J}^{+}(0)=\epsilon_{j}(0)$ and
show that $\frac{z^{2}}{2C(V+z)}\rightarrow\infty$ as $n\rightarrow\infty$
then we will have shown that $\mathbb{P}(Y_{J}^{+}(i)<0\text{ for all }i)$
goes to $1$ as $n$ goes to infinity. This along with the analogous statement
of $Y_{J}^{-}$ and a union bound argument will show that the inequalities in
Lemma 5 hold.

We now compute $C$ and $V$. From the absolute bound on the one step change in
$Y_{J}$ we know that

$\displaystyle|\Delta Y_{J}(0)|$
$\displaystyle\leq\binom{q-1}{1}\binom{n-j}{q-j-1}$

So we can take $C=\binom{q-1}{1}\binom{n-j}{q-j-1}$ Furthermore, Lemma 6
implies that

$\displaystyle\sum_{i\geq 0}\mathbb{E}(|\Delta
Y_{J}^{+}(i)|\,|\,\mathcal{F}_{i})$
$\displaystyle\leq\frac{n(n-1)}{q(q-1)}O\left(\frac{\sup_{t\in[0,t_{m_{0}}]}|\epsilon_{j}^{\prime}(t)|}{n(n-1)}\right)$
$\displaystyle\leq\frac{n(n-1)}{q(q-1)}O\left(\left|\frac{{n-j\choose
q-j}n^{-1+3\beta{q\choose
2}}q^{f}n^{\beta\left(\binom{j}{2}+2\binom{q}{2}+1\right)}(-{j\choose
2}-2{q\choose 2})(-q(q-1))}{n(n-1)}\right|\right)$
$\displaystyle=O\left(\binom{n-j}{q-j}q^{f+2}n^{-1+6\beta\binom{q}{2}}\right)$

Hence, we can set
$V=O\left(\binom{n-j}{q-j}q^{f+2}n^{-1+6\beta\binom{q}{2}}\right)$.

Set $z=\epsilon_{j}(0)={n-j\choose q-j}n^{-1+3\beta{q\choose 2}}q^{f}$. Notice
that $z\ll V$, so to verify that $\frac{z^{2}}{2C(V+z)}\gg 1$, it suffices to
check that $\frac{z^{2}}{CV}\gg 1$. Observe that

$\displaystyle\frac{z^{2}}{CV}$ $\displaystyle=\frac{{n-j\choose
q-j}^{2}n^{-2+6\beta{q\choose
2}}q^{2f}}{O\left(\binom{n-j}{q-j}q^{f+2}n^{-1+6\beta\binom{q}{2}}\right)\cdot\binom{q-1}{1}\binom{n-j}{q-j-1}}$
$\displaystyle=\Omega\left(\frac{n-q+1}{q-j}n^{-1}q^{f-3}\right)$
$\displaystyle=\Omega\left(\left(1-\frac{q}{n}+\frac{1}{n}\right)q^{f-4}\right)$
$\displaystyle=\Omega(q^{f-4})$

Since $f>4$, this shows $\frac{z^{2}}{CV}\gg 1$. To get the conclusion of
Lemma 5, we show $\mathbb{P}(\mathcal{G}_{m_{0}}^{c})\rightarrow 0$ as
$n\rightarrow\infty$. Observe that

$\displaystyle\mathbb{P}(\mathcal{G}_{m_{0}}^{c})$
$\displaystyle\leq\mathbb{P}\left(\bigcup_{J\subset[n],|J|<q}\left\\{Y_{J}^{+}(i)\geq
0\text{ for some }i\geq 0\right\\}\cup\left\\{Y_{J}^{-}(i)\leq 0\text{ for
some }i\geq 0\right\\}\right)$ $\displaystyle\leq
2q\binom{n}{q}e^{-\Omega(q^{f-4})}$ $\displaystyle\leq
2q\left(\frac{en}{q}\right)^{q}e^{-\Omega(q^{f-4})}$

Observe that

$\log\left(q\left(\frac{en}{q}\right)^{q}\right)=\log q+q+q\log n-q\log q$

Since the largest (in the asymptotic sense) term is $q\log n$ we need to
verify that that $q\log n\ll q^{f-4}$. To see this note that
$f\gg\frac{\log\log n}{\log q}$. Hence,
$2q\left(\frac{en}{q}\right)^{q}e^{-\Omega(q^{f-4})}=o(1)$ and we have
$\mathbb{P}(\mathcal{G}_{m_{0}})\rightarrow 1$ as $n\rightarrow\infty$ which
proves Lemma 5.

###  3.6 Appendix

####  3.6.1 Proof of Lemma 6

We now prove Lemma 6.

We first show that
$\left(\binom{q}{2}-\binom{j}{2}\right)\frac{y_{j}y_{2}}{h}=\frac{y_{j}^{\prime}}{n^{2}}$

$\displaystyle({q\choose 2}-{j\choose 2})\frac{y_{j}y_{2}}{h}$
$\displaystyle=({q\choose 2}-{j\choose 2})\frac{{n-j\choose q-j}p^{{q\choose
2}-{j\choose 2}}{n-2\choose q-2}p^{{q\choose 2}-1}}{{n\choose q}p^{q\choose
2}}$ $\displaystyle=({q\choose 2}-{j\choose 2}){n-j\choose
q-j}\frac{q(q-1)}{n(n-1)}p^{{q\choose 2}-{j\choose 2}-1}$
$\displaystyle=\frac{y_{j}^{\prime}}{n(n-1)}$

Next, we show that
$\binom{q}{2}\frac{y_{j}\epsilon_{2}}{h}\leq\frac{1}{2}\frac{\epsilon_{j}^{\prime}}{n(n-1)}$.
Indeed

$\displaystyle\binom{q}{2}\frac{y_{j}\epsilon_{2}}{h}(\frac{\epsilon_{j}^{\prime}}{n(n-1)})^{-1}$
$\displaystyle=\frac{(\frac{\binom{q}{2}\binom{n-j}{q-j}p^{\binom{q}{2}-\binom{j}{2}}\binom{n-2}{q-2}n^{-1+3\beta\binom{q}{2}}q^{f}p^{-\binom{2}{2}-2\binom{q}{2}}}{\binom{n}{q}p^{\binom{q}{2}}})}{(\frac{\binom{n-j}{q-j}n^{-1+3\beta\binom{q}{2}}q^{f}p^{-\binom{j}{2}-2\binom{q}{2}-1}(\binom{j}{2}+2\binom{q}{2})(q(q-1))}{n(n-1)})}$
$\displaystyle=\frac{\binom{q}{2}}{\binom{j}{2}+2\binom{q}{2}}\leq\frac{1}{2}$

To prove the rest of Lemma 6, we will first give a lower bound on
$\frac{\epsilon_{j}^{\prime}}{n(n-1)}$ and then prove this is asymptotically
larger than all the remaining terms. First notice that

$\displaystyle\frac{\epsilon_{j}^{\prime}}{n(n-1)}$
$\displaystyle=\frac{\binom{n-j}{q-j}n^{-1+3\beta\binom{q}{2}}q^{f}p^{-\binom{j}{2}-2\binom{q}{2}-1}(\binom{j}{2}+2\binom{q}{2})(q(q-1))}{n(n-1)}$
$\displaystyle=\Omega(\binom{n-j}{q-j}n^{-3+3\beta\binom{q}{2}}q^{f+4}p^{-\binom{j}{2}-2\binom{q}{2}-1})$

Now, we will compute $q\binom{q}{m}\frac{y_{j}y_{m}}{h}$ where $3\leq m\leq
q-1$ and show that each of these terms is
$o(\binom{n-j}{q-j}n^{-3+3\beta\binom{q}{2}}q^{f+4}p^{-\binom{j}{2}-2\binom{q}{2}-1})$.

$\displaystyle q\binom{q}{m}\frac{y_{j}y_{m}}{h}$
$\displaystyle=q\binom{q}{m}\frac{\binom{n-j}{q-j}p^{\binom{q}{2}-\binom{j}{2}}\binom{n-m}{q-m}p^{\binom{q}{2}-\binom{m}{2}}}{\binom{n}{q}p^{\binom{q}{2}}}$
$\displaystyle\leq\binom{n-j}{q-j}q(\frac{qe}{m})^{m}(\frac{ne}{q-m})^{q-m}(\frac{q}{n})^{q}p^{-\binom{q}{2}}$
$\displaystyle\leq(\binom{n-j}{q-j}n^{-m+\beta\binom{q}{2}}q^{2m+1}e^{q}m^{-m})$
$\displaystyle=o(\binom{n-j}{q-j}n^{-3+3\beta\binom{q}{2}}q^{f+4}p^{-\binom{j}{2}-2\binom{q}{2}-1})$

Next, notice that since for all $3\leq m\leq q-1$ we have that
$\epsilon_{m}=o(y_{m})$ then

$q\binom{q}{m}\frac{y_{j}\epsilon_{m}}{h}=o(q\binom{q}{m}\frac{y_{j}y_{m}}{h})=o(\binom{n-j}{q-j}n^{-3+3\beta\binom{q}{2}}q^{f+4}p^{-\binom{j}{2}-2\binom{q}{2}-1})$

Lastly, we need to verify that
$\frac{\sup_{s}\in[0,\frac{m_{0}}{n(n-1)}]|y_{j}^{\prime\prime}(s)|}{2n^{2}(n-1)^{2}}$
and
$\frac{\sup_{s\in[0,\frac{m_{0}}{n(n-1)}]}|\epsilon_{j}^{\prime\prime}(s)|}{2n^{2}(n-1)^{2}}$
are also both
$o(\binom{n-j}{q-j}n^{-3+3\beta\binom{q}{2}}q^{f+4}p^{-\binom{j}{2}-2\binom{q}{2}-1})$.

$\displaystyle\frac{\sup_{s}\in[0,\frac{m_{0}}{n(n-1)}]|y_{j}^{\prime\prime}(s)|}{2n^{2}(n-1)^{2}}$
$\displaystyle=\frac{\binom{n-j}{q-j}(p(0))^{\binom{q}{2}-\binom{j}{2}-2}(\binom{q}{2}-\binom{j}{2})(\binom{q}{2}-\binom{j}{2}-1)(q^{2}(q-1)^{2})}{2n^{2}(n-1)^{2}}$
$\displaystyle=O(\binom{n-j}{q-j}n^{-4}q^{8})$
$\displaystyle=o(\binom{n-j}{q-j}n^{-3+3\beta\binom{q}{2}}q^{f+4}p^{-\binom{j}{2}-2\binom{q}{2}-1})$

Similarly, we compute

$\displaystyle\frac{\sup_{s\in[0,\frac{m_{0}}{n(n-1)}]}|\epsilon_{j}^{\prime\prime}(s)|}{2n^{2}(n-1)^{2}}$
$\displaystyle\leq
O\left(\frac{\binom{n-j}{q-j}n^{-1+3\beta\binom{q}{2}}q^{f+8}(p(\frac{m_{0}}{n(n-1)}))^{-\binom{j}{2}-2\binom{q}{2}-2}}{n^{2}(n-1)^{2}}\right)$
$\displaystyle=O(\binom{n-j}{q-j}n^{-5+\beta(6\binom{q}{2}+2)}q^{f+8})$
$\displaystyle=o(\binom{n-j}{q-j}n^{-3+3\beta\binom{q}{2}}q^{f+4}p^{-\binom{j}{2}-2\binom{q}{2}-1})$

This completes the proof of Lemma 6.

####  3.6.2 Proof of Combinatorial Identities

We first show that $\sum_{m=2}^{\ell}\binom{\ell}{m}(-1)^{m}(m-1)=1$. Observe
that

$\frac{(1+x)^{\ell}-1}{x}=\sum_{m=1}^{\ell}\binom{\ell}{m}x^{m-1}$

This means

$\frac{d}{dx}\left[\frac{(1+x)^{\ell}-1}{x}\right]=\sum_{m=2}^{\ell}\binom{\ell}{m}(m-1)x^{m-2}$

Letting $x=-1$ yields $\sum_{m=2}^{\ell}\binom{\ell}{m}(-1)^{m}(m-1)=1$.

We now show that
$\sum_{m=2}^{\ell}\binom{\ell}{m}(-1)^{m}(m-1)+\sum_{m=1}^{\ell}\binom{\ell}{m}(-1)^{m+1}m=1$.
Observe that

$(1+x)^{\ell}=\sum_{m=0}^{\ell}\binom{\ell}{m}x^{m}$

Differentiating and letting $x=-1$ yields
$\sum_{m=1}^{\ell}\binom{\ell}{m}(-1)^{m+1}m=0$, so we have
$\sum_{m=2}^{\ell}\binom{\ell}{m}(-1)^{m}(m-1)+\sum_{m=1}^{\ell}\binom{\ell}{m}(-1)^{m+1}m=1$.

We now show that

$\sum_{0\leq m_{1}\leq k,1\leq m_{2}\leq\ell,m_{1}+m_{2}\geq
2}\binom{k}{m_{1}}\binom{\ell}{m_{2}}(-1)^{m_{1}+m_{2}}(m_{1}+m_{2}-1)=0$

We show this by verifying that

$\sum_{0\leq m_{1}\leq k,0\leq m_{2}\leq\ell,m_{1}+m_{2}\geq
2}\binom{k}{m_{1}}\binom{\ell}{m_{2}}(-1)^{m_{1}+m_{2}}(m_{1}+m_{2}-1)=1$

and the $m_{2}=0$ part

$\sum_{0\leq m_{1}\leq k,m_{1}\geq
2}\binom{k}{m_{1}}\binom{\ell}{0}(-1)^{0+m_{1}}(0+m_{1}-1)=1$

This second equality is the same as the first identity we proved. For the
first one, observe that

$\frac{(1+x)^{k+\ell}-1}{x}=\frac{(1+x)^{k}(1+x)^{\ell}-1}{x}=\sum_{0\leq
m_{1}\leq k,0\leq m_{2}\leq\ell,m_{1}+m_{2}\geq
1}\binom{k}{m_{1}}\binom{\ell}{m_{2}}x^{m_{1}+n_{1}-1}$

This implies

$\frac{d}{dx}\left[\frac{(1+x)^{k+\ell}-1}{x}\right]=\sum_{0\leq m_{1}\leq
k,0\leq m_{2}\leq\ell,m_{1}+m_{2}\geq
2}\binom{k}{m}\binom{\ell}{n}(m_{1}+m_{2}-1)x^{m_{1}+m_{2}-2}$

Substitution $x=-1$ yields

$\sum_{0\leq m_{1}\leq k,0\leq m_{2}\leq\ell,m_{1}+m_{2}\geq
2}\binom{k}{m_{1}}\binom{\ell}{m_{2}}(-1)^{m_{1}+m_{2}}(m_{1}+m_{2}-1)=1$

##  4 Acknowledgements

We would like to thank Dhruv Mubayi for the ideas used in Proposition 2 and
his guidance throughout. This work was funded by NSF DMS-1763317.

## References

  * [1] Patrick Bennett.  The sum-free process.  arXiv preprint arXiv:1502.01644, 2015.
  * [2] Patrick Bennett and Tom Bohman.  A note on the random greedy independent set algorithm.  Random Structures & Algorithms, 49(3):479–502, 2016.
  * [3] Patrick Bennett and Andrzej Dudek.  A gentle introduction to the differential equation method and dynamic concentration.  Discrete Mathematics, 345(12):113071, 2022.
  * [4] Tom Bohman.  The triangle-free process.  Advances in Mathematics, 221(5):1653–1677, 2009.
  * [5] Tom Bohman and Lutz Warnke.  Large girth approximate steiner triple systems.  Journal of the London Mathematical Society, 100(3):895–913, 2019\.
  * [6] Béla Bollobás and Oliver Riordan.  Constrained graph processes.  the electronic journal of combinatorics, 7:R18–R18, 2000.
  * [7] William Duckworth and Nicholas C Wormald.  Minimum independent dominating sets of random cubic graphs.  Random Structures & Algorithms, 21(2):147–161, 2002.
  * [8] Paul Erdös, Stephen Suen, and Peter Winkler.  On the size of a random maximal graph.  Random Structures & Algorithms, 6(2-3):309–318, 1995.
  * [9] David A Freedman.  On tail probabilities for martingales.  the Annals of Probability, pages 100–118, 1975.
  * [10] Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, and Lyuben Lichev.  Conflict-free hypergraph matchings.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2991–3005. SIAM, 2023.
  * [11] Jeong Han Kim.  The ramsey number $r(3,t)$ has order of magnitude $t^{2}/\log\,t$.  Random Structures & Algorithms, 7(3):173–207, 1995.
  * [12] Deryk Osthus and Anusch Taraz.  Random maximal $h$-free graphs.  Random Structures & Algorithms, 18(1):61–82, 2001.
  * [13] Nicholas C Wormald et al.  The differential equation method for random graph processes and greedy algorithms.  Lectures on approximation and randomized algorithms, 73:73–155, 1999.