Some problems in the theory of pseudo-random graphs

NEW

Problem: For fixed odd $k\ge 5$, interpret an $(n,d,\lambda)$-graph as a finite simple $d$-regular graph on $n$ vertices whose nontrivial adjacency eigenvalues have absolute value at most $\lambda$. The conjecture asserts that if

then the minimum number of edges to delete from $G$ to make it $C_k$-free is $(1/4+o(1))nd$.

Result: The statement is false.

Let $g=k+2$, still odd. For $t\to\infty$, let $G_t$ be the balanced blow-up of the cycle $C_g$: replace each vertex of $C_g$ by an independent set of size $t$, and replace each edge of $C_g$ by a complete bipartite graph between the corresponding parts.

Then

The adjacency matrix is $A(C_g)\otimes J_t$, so the nonzero eigenvalues are

Thus the largest nontrivial absolute eigenvalue is

Hence

so the hypothesis holds.

But $G_t$ is $C_k$-free. Indeed, any $C_k$ in $G_t$ would project to a closed walk of length $k$ in $C_g$. Such a walk has steps $\pm1$ modulo $g$, so the sum of its $k$ steps is congruent to $0\pmod g$. Since $k<g$, the only possible multiple of $g$ is $0$; but a sum of $k$ many $\pm1$’s is odd, hence cannot be $0$. Contradiction.

Therefore $G_t$ is already $C_k$-free, so its deletion resilience toward becoming $C_k$-free is $0$, not $(1/4+o(1))nd$. Equivalently, $\operatorname{ex}(G_t,C_k)=e(G_t)=nd/2$, not $(1/4+o(1))nd$.

The defect is not merely bipartiteness: these $G_t$ are connected and non-bipartite with $\lambda<d$. The hypothesis $d^{k-1}\gg\lambda^{k-2}$ is simply too weak; a natural repair would need an additional density/pseudorandomness condition involving $n$, such as the commonly appearing stronger form $d^{k-1}/n\gg\lambda^{k-2}$.

Citation: No external citation is needed; the counterexample is explicit.