Exponential Independence in Subcubic Graphs

NEW

Problem: Reconstructed statement: for finite simple trees $T$ with maximum degree $\Delta(T)\le 4$, does there exist an absolute constant $c>0$ such that

$$\alpha_e(T)\ge c|V(T)|?$$

Here $S\subseteq V(T)$ is exponentially independent if, for every $u\in S$,

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

where $d_{(T,X)}(u,v)$ is the length of a shortest $u$-$v$ path having no internal vertex in $X$, and $2^{-\infty}=0$. This is the standard formal meaning of “exponentially independent sets of linear order.”

Result: Yes. In fact,

$$\alpha_e(T)\ge \frac{|V(T)|}{800}$$

for every finite tree $T$ with $\Delta(T)\le4$.

Proof. For a tree $T$, define the ordinary energy

$$E(T)=\sum_{\substack{x,y\in V(T)\\x\ne y}}2^{1-d_T(x,y)}.$$

We first prove $E(T)\le 200|V(T)|$.

Root $T$ at a leaf. Then every vertex has at most three children. For a rooted tree $R$ with at most three children per vertex, root $r$, put

$$A(R)=\sum_{x\in V(R)}2^{-d_R(r,x)}.$$

We prove by induction that

$$E(R)\le 200|V(R)|-5A(R)^2.$$

Let the child subtrees of $r$ be $R_1,\dots,R_m$, $m\le3$, and set $A_i=A(R_i)$, $a_i=A_i/2$, $s=\sum a_i$, $p=\sum a_i^2$, $q=\sum_{i<j}a_ia_j$. Then

$$A(R)=1+s$$

and energy decomposition gives

$$E(R)=\sum_i E(R_i)+2\sum_i A_i+\frac12\sum_{i\ne j}A_iA_j.$$

Using induction,

$$E(R)\le 200(|V(R)|-1)-20p+4s+4q.$$

Since $m\le3$, we have $q\le p$ and $p\ge s^2/3$. Hence

$$5(1+s)^2+4s+4q-20p =5+14s-15p+14q \le 5+14s-p \le 5+14s-\frac{s^2}{3} \le 152<200.$$

Therefore $E(R)\le 200|V(R)|-5A(R)^2$. Thus $E(T)\le200|V(T)|$.

Now select each vertex independently with probability $\rho=1/400$. For a selected vertex $u$, let

$$W(u)=\sum_{\substack{v\in R\\v\ne u}}2^{1-d_T(u,v)}.$$

Call $u$ bad if $W(u)\ge1$, and delete all bad selected vertices. The remaining set is $S$. Since $\mathbf 1_{\{u\text{ bad}\}}\le W(u)$,

$$\mathbb E|S| \ge \rho n-\rho^2E(T) \ge \frac{n}{400}-\frac{200n}{400^2} =\frac{n}{800}.$$

So some outcome has $|S|\ge n/800$.

For every $u\in S$,

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

Because $d_{(T,S\setminus\{u\})}(u,v)\ge d_T(u,v)$, the exponential-independence weight is no larger than this ordinary sum. Hence $S$ is exponentially independent.

Thus trees of maximum degree at most $4$ do have exponentially independent sets of linear order.

Citation: No known prior resolution is used here. The problem statement is from Bessy, Pardey, and Rautenbach, “Exponential Independence in Subcubic Graphs,” Conclusion section.