Simultaneous Control of Cycles and Independent Sets

Why the Two Requirements Must Be Controlled Together

A random graph may have few short cycles on average, and it may have few large independent sets on average, without those two properties occurring in the same graph. To establish existence with both properties, we need to control the probability that either requirement fails. A union bound does this without requiring the events to be independent.

We work with the binomial random graph $G(n,p)$: its vertex set has $n$ vertices, and each possible edge is included independently with probability $p$, where $0\le p\le1$. Fix an integer $g\ge4$. A short cycle in this tutorial means a cycle of length less than $g$. We will count vertices lying on such cycles, rather than only counting the cycles, because deleting those vertices removes every short cycle at once.

Definition: For a graph $G$, let $X(G)$ be the number of vertices that lie on at least one cycle of length less than $g$. For a positive integer $r$, let $Y_r(G)$ be the number of independent vertex sets of size $r$. An independent set is a set of vertices no two of which are adjacent.

We use two elementary probability inequalities. If $Z$ is a nonnegative random variable and $a>0$, then $\Pr(Z\ge a)\le \mathbb{E}Z/a$: indeed, $Z\ge a$ on the event in question, so $\mathbb{E}Z\ge a\Pr(Z\ge a)$. In particular, for a nonnegative integer-valued $Y$, $\Pr(Y\ge1)\le\mathbb{E}Y$. These inequalities turn expected counts into bounds on failure probabilities.

The Joint-Control Principle

Theorem: Suppose $G$ is a random graph on $n$ vertices and $$ \frac{2\mathbb{E}X(G)}{n}+\mathbb{E}Y_r(G)<1. $$ Then there is an outcome $G$ for which $X(G)<n/2$ and $Y_r(G)=0$. Deleting all vertices that lie on cycles of length less than $g$ leaves an induced subgraph $H$ with more than $n/2$ vertices, no cycle of length less than $g$, and $\alpha(H)\le r-1$.

Proof. The probability that $X(G)\ge n/2$ is at most $2\mathbb{E}X(G)/n$, by the nonnegative-variable inequality. The probability that $Y_r(G)\ge1$ is at most $\mathbb{E}Y_r(G)$. By the union bound, the probability that at least one of these two failures occurs is at most their sum, which is less than $1$. Thus at least one outcome has both $X(G)<n/2$ and $Y_r(G)=0$.

For that outcome, let $S$ consist of the vertices that lie on cycles of length less than $g$, and take $H=G[V(G)\setminus S]$, the induced subgraph on the remaining vertices. Since $|S|=X(G)<n/2$, we have $|V(H)|=n-X(G)>n/2$. If $H$ contained a cycle of length less than $g$, all vertices of that cycle would also be vertices of $G$ lying on such a cycle, and so would belong to $S$, contrary to their presence in $H$. Finally, $Y_r(G)=0$ means that $G$ has no independent set of size $r$. An independent set in $H$ is also independent in $G$, because $H$ is induced. Therefore $H$ has no independent set of size $r$, so $\alpha(H)\le r-1$. $\square$

The condition is deliberately phrased as a sum of failure probabilities. It does not claim that the event of having few short-cycle vertices and the event of having no independent $r$-set are independent events.

Estimating the Two Expectations

For each integer $\ell\ge3$, let $C_\ell(G)$ denote the number of cycles of length $\ell$ in $G$. A specified cycle of length $\ell$ requires $\ell$ specified edges, so in $G(n,p)$ its probability of appearing is $p^\ell$. There are $(n)_\ell/(2\ell)$ possible cycles, where $(n)_\ell=n(n-1)\cdots(n-\ell+1)$: order the $\ell$ distinct vertices, then divide by the $\ell$ choices of starting point and the two directions of traversal. Hence $$ \mathbb{E}C_\ell(G)=\frac{(n)_\ell}{2\ell}p^\ell. $$

Each short cycle of length $\ell$ contains $\ell$ vertices. Counting a vertex more than once only increases the count, so $X(G)\le\sum_{\ell=3}^{g-1}\ell C_\ell(G)$. Taking expectations gives the useful bound $$ \mathbb{E}X(G)\le \sum_{\ell=3}^{g-1}\frac{(n)_\ell}{2}p^\ell \le \frac12\sum_{\ell=3}^{g-1}(np)^\ell. $$

For independent sets, each fixed $r$-vertex set is independent precisely when all $\binom r2$ possible edges within it are absent. That probability is $(1-p)^{\binom r2}$, and there are $\binom nr$ such sets. By summing their indicator variables, $$ \mathbb{E}Y_r(G)=\binom nr(1-p)^{\binom r2} \le \left(\frac{en}{r}\right)^r\exp\left(-\frac{p\,r(r-1)}2\right), $$

when $1\le r\le n$. Here we used $\binom nr\le(en/r)^r$ and $1-p\le e^{-p}$. The first estimate gets smaller when $np$ is small; the second gets smaller when $p r$ is sufficiently large compared with $\log(en/r)$. The parameter choice must satisfy both demands.

Worked Example: Counting Short-Cycle Vertices by an Upper Bound

Take $G(5,1/2)$ and $g=4$, so the short cycles are triangles. There are $\binom53=10$ possible triangles. Each requires three edges, so its probability is $(1/2)^3=1/8$. Thus $$ \mathbb{E}C_3(G)=10\cdot\frac18=\frac54. $$

Every triangle contains three vertices, and the number of vertices lying on triangles is at most three times the number of triangles. Therefore $$ \mathbb{E}X(G)\le3\mathbb{E}C_3(G)=3\cdot\frac54=\frac{15}{4}. $$

Check: The upper bound $15/4$ is for the number of vertices on triangles, not the expected number of triangles. It can exceed $5$, the total number of vertices, because counting three vertices per triangle counts vertices repeatedly. The bound is valid but not necessarily sharp.

Worked Example: The First Moment for Independent Triples

In $G(6,1/2)$, let $Y_3$ count independent sets of size $3$. There are $\binom63=20$ candidate triples. A particular triple has $\binom32=3$ possible internal edges, all of which must be absent; its probability of being independent is $(1/2)^3=1/8$. Therefore $$ \mathbb{E}Y_3=20\cdot\frac18=\frac52. $$

The first-moment inequality gives $\Pr(Y_3\ge1)\le5/2$, which is true but uninformative because probabilities are also at most $1$. This computation is a useful warning: knowing how to form the expectation does not guarantee that a chosen $n,p,r$ makes the resulting probability bound small.

Check: The expected count is $5/2$, not the probability of having an independent triple. A graph can have several such triples, so an expected count can exceed $1$.

A Parameter Choice That Works for Large Graphs

The two estimates can be made compatible for every fixed $g\ge4$. Write $\log$ for the natural logarithm, and set $$ \varepsilon=\frac{1}{2g},\qquad p=n^{-1+\varepsilon},\qquad r=\left\lceil4n^{1-\varepsilon}\log n\right\rceil. $$

We show that for all sufficiently large $n$, the joint-control theorem applies. First, $np=n^\varepsilon$. The short-cycle estimate therefore gives $$ \mathbb{E}X(G)\le\frac12\sum_{\ell=3}^{g-1}n^{\varepsilon\ell} \le\frac{g-3}{2}n^{\varepsilon(g-1)}. $$

Since $\varepsilon(g-1)=(g-1)/(2g)<1$, the right-hand side is less than $n/4$ for all sufficiently large $n$. Consequently $2\mathbb{E}X(G)/n<1/2$.

Now consider independent sets. For sufficiently large $n$, $1\le r\le n$, so the first-moment estimate applies. Since $r\ge4n^{1-\varepsilon}\log n$, we have $r/n\ge4n^{-\varepsilon}\log n$. Thus $$ \log\left(\frac{en}{r}\right) \le 1+\varepsilon\log n-\log(4\log n) \le 1+\varepsilon\log n. $$

Also $pr\ge4\log n$, and $p\le1$, so $p(r-1)=pr-p\ge4\log n-1$. Taking logarithms in the first-moment bound and using these two inequalities yields $$ \log\mathbb{E}Y_r(G) \le r\left(1+\varepsilon\log n-\frac{4\log n-1}{2}\right) =r\left(\frac32-(2-\varepsilon)\log n\right). $$

Because $\varepsilon\le1/8$, the quantity in parentheses is at most $-\log n$ once $n$ is sufficiently large: it is enough that $(1-\varepsilon)\log n\ge3/2$. Hence $\mathbb{E}Y_r(G)\le n^{-r}<1/4$ for sufficiently large $n$. Combining the bounds gives $$ \frac{2\mathbb{E}X(G)}{n}+\mathbb{E}Y_r(G)<\frac12+\frac14<1. $$

Conclusion: For each fixed integer $g\ge4$ and all sufficiently large $n$, there is a graph $H$ with more than $n/2$ vertices, no cycle of length less than $g$, and $\alpha(H)\le r-1$, where $r=\lceil4n^{1-1/(2g)}\log n\rceil$.

The conclusion follows by applying the joint-control theorem to $G(n,p)$, then deleting every vertex lying on a short cycle. The probability argument selects one graph where both bounds hold; the deletion step removes the cycles without increasing the independence number.

Worked Example: A Small Graph Satisfying Both Conditions

Let $G$ have vertex set $\{1,2,3,4\}$ and edge set $\{12,23,34,41\}$. This is a particular outcome of $G(4,1/2)$, and its probability is $1/2^6=1/64$, because four specified edges are present and the other two possible edges, $13$ and $24$, are absent.

For $g=4$, the only possible short cycles are triangles. The graph has no triangle: among its four possible triples, $\{1,2,3\}$ lacks $13$, $\{1,2,4\}$ lacks $24$, $\{1,3,4\}$ lacks $13$, and $\{2,3,4\}$ lacks $24$. Thus $X(G)=0$.

The pairs $\{1,3\}$ and $\{2,4\}$ are independent, so $Y_2(G)\ge2$. No triple is independent: each of the four triples contains at least one of the four cycle edges. Hence $Y_3(G)=0$, and $\alpha(G)=2$.

Check: With $r=3$, this graph already has no short cycle and no independent set of size $r$; no deletion is needed. Its probability $1/64$ is a direct check that the joint event can occur in this small example. The general proof is stronger: it establishes existence by bounding the total probability of either failure.

Common Pitfalls and What the Argument Gives

Do not add expectations and call the result a joint probability. The quantities $\mathbb{E}X$ and $\mathbb{E}Y_r$ are expected counts. They yield failure-probability bounds through the nonnegative-variable inequality; the union bound then combines those probabilities.

Count vertices, not just cycles, when planning deletion. A bound on the number of short cycles alone does not directly say how many vertices must be removed if cycles overlap. The inequality $X\le\sum_{\ell=3}^{g-1}\ell C_\ell$ provides a valid upper bound on the number of vertices to delete, including when some vertices lie on multiple short cycles.

Deletion preserves the independent-set restriction in the needed direction. Every independent set in the remaining induced subgraph is also an independent set in the original graph. Thus deleting vertices cannot create a larger independent set than the original graph had. The argument does not assert that the independence number stays equal.

Check Your Understanding

Use the definitions and estimates above to answer the following.

For $G(n,p)$, derive the probability that one specified set of $r$ vertices is independent.
Why is the number of vertices on short cycles at most $\sum_{\ell=3}^{g-1}\ell C_\ell(G)$, even when cycles overlap?
Explain why $2\mathbb{E}X/n+\mathbb{E}Y_r<1$ guarantees an outcome where $X<n/2$ and $Y_r=0$.
In the four-cycle example, verify directly that every three-vertex subset contains an edge.
Explain why taking an induced subgraph after deleting all vertices on short cycles cannot create a new short cycle.