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

$$d^{k-1}\gg \lambda^{k-2},$$

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

$$n=gt,\qquad d=2t.$$

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

$$2t\cos(2\pi j/g),\qquad j=0,\dots,g-1.$$

Thus the largest nontrivial absolute eigenvalue is

$$\lambda=2t\cos(\pi/g)<2t=d.$$

Hence

$$\frac{d^{k-1}}{\lambda^{k-2}} = \frac{(2t)^{k-1}}{(2t\cos(\pi/g))^{k-2}} = \frac{2t}{\cos(\pi/g)^{k-2}} \to\infty,$$

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.