Exponential Independence in Subcubic Graphs

NEW

Problem: For a finite simple graph $G$ and $S\subseteq V(G)$, let

$$d_{(G,S)}(u,v)=\operatorname{dist}_{G-(S\setminus\{u,v\})}(u,v),$$

with value $\infty$ if no such path exists. A set $S$ is exponentially independent if, for every $u\in S$,

$$\sum_{v\in S\setminus\{u\}}2^{1-d_{(G,S)}(u,v)}<1.$$

The question is whether there is a constant $c>0$ such that every finite subcubic graph $G$ of order $n$ satisfies $\alpha_e(G)\ge cn$.

This is the natural formalization of “subcubic graphs have exponentially independent sets of linear order” in the cited paper.

Result: The answer is no. There is a sequence of connected cubic graphs $G_m$ with $|V(G_m)|\to\infty$ and

$$\frac{\alpha_e(G_m)}{|V(G_m)|}\to 0.$$

Proof sketch with full logical core:

Let $T_3$ be the infinite cubic tree. For $S\subseteq V(T_3)$, define

$$f(x,S)=\limsup_{k\to\infty}\frac{|S\cap B_k(x)|}{|B_k(x)|}.$$

Key lemma. If $S\subseteq V(T_3)$ satisfies

$$\sum_{v\in S\setminus\{u\}}2^{1-d_{(T_3,S)}(u,v)}\le 1 \quad\text{for every }u\in S,$$

then $f(x,S)=0$ for every $x\in V(T_3)$.

This is the same argument as Bessy–Pardey–Rautenbach’s infinite-tree theorem, with “$<1$” replaced by “$\le1$”. Indeed, if $f(u,S)>0$ for some $u\in S$, root $T_3$ at $u$. Let $X_i$ be the first vertices of $S$ at distance $i$ from $u$ along the rooted branches. Writing $\vec f(x)$ for the upper density of $S$ in the descendant cone of $x$, one obtains

$$f(u,S)\le \frac13\sum_{i\ge1}\sum_{x\in X_i}2^{1-i}\vec f(x).$$

Also $f(x,S)\ge \frac23\vec f(x)$. If every $x\in X=\bigcup_i X_i$ had $f(x,S)<2f(u,S)$, then $\vec f(x)<3f(u,S)$, forcing

$$\sum_{i,x}2^{1-i}>1,$$

contrary to the assumed weight bound at $u$. Hence some $x\in S$ has $f(x,S)\ge2f(u,S)$. Iterating gives densities exceeding $1$, impossible.

Now choose connected cubic graphs $G_m$ with girth $\to\infty$, whose existence is classical. Suppose, toward contradiction, that some $\varepsilon>0$ and exponentially independent sets $S_m\subseteq V(G_m)$ satisfy $|S_m|\ge\varepsilon |V(G_m)|$.

Take a local weak limit of the rooted marked graphs $(G_m,S_m,o_m)$, where $o_m$ is uniformly random. Since the girth tends to infinity, the underlying limit is $T_3$. For every fixed $k$,

$$\mathbb E\frac{|S\cap B_k(o)|}{|B_k(o)|} = \lim_m \frac{|S_m|}{|V(G_m)|} \ge \varepsilon,$$

because in a high-girth cubic graph every radius-$k$ ball has size $3\cdot2^k-2$. Therefore, by Fatou,

$$\mathbb E f(o,S)\ge \varepsilon,$$

so with positive probability $f(o,S)>0$.

On the other hand, exponential independence of each $S_m$ implies that no selected vertex has truncated exponential weight $>1$. This is a local property, so it passes to the limit: almost surely, every $u\in S$ in the limiting subset of $T_3$ has total exponential weight at most $1$. The key lemma then forces $f(o,S)=0$ almost surely, contradiction.

Thus no positive linear lower bound exists.

Citation: Definitions and the infinite cubic tree argument originate in Bessy, Pardey, and Rautenbach, “Exponential independence in subcubic graphs,” Discrete Mathematics 344 (2021), 112439. Existence of connected cubic graphs of arbitrarily large girth is due to Erdős and Sachs, 1963.