AUTOMATED CONJECTURING VII: THE GRAPH BRAIN PROJECT & BIG MATHEMATICS

NEW

Problem: Reconstructed statement: for every finite simple graph $G$,

$$\alpha(G)\ge \lceil \vartheta(G)\rceil-g(G),$$

where $\alpha$ is independence number, $\vartheta$ is the usual Lovász theta number satisfying $\alpha(G)\le \vartheta(G)$, and $g(G)$ is girth. The conjecture text lists exactly these graph invariants. The counterexample below is connected and has a triangle, so it is unaffected by common connectedness or girth-convention ambiguities.

Result: The statement is false.

Let $H$ be the disjoint union of $13$ copies of $C_5$, and let

$$G=K_1\vee H$$

be the join of $H$ with one new universal vertex.

Standard theta facts: $\vartheta(C_5)=\sqrt5$, $\vartheta$ is additive on disjoint unions, and

$$\vartheta(A\vee B)=\max\{\vartheta(A),\vartheta(B)\}.$$

Hence

$$\vartheta(G)=\vartheta(H)=13\sqrt5.$$

Since $29^2<13^2\cdot 5<30^2$, we have

$$\lceil \vartheta(G)\rceil=\lceil 13\sqrt5\rceil=30.$$

Also, each $C_5$ has independence number $2$, so

$$\alpha(H)=26.$$

The universal vertex cannot be used together with any vertex of $H$, hence

$$\alpha(G)=26.$$

Finally, $G$ contains a triangle: the universal vertex together with any edge of a $C_5$. Thus

$$g(G)=3.$$

Therefore the conjectured inequality gives

$$26=\alpha(G)\ge \lceil\vartheta(G)\rceil-g(G)=30-3=27,$$

which is false. So this connected $66$-vertex graph is a counterexample.

Citation: The theta facts used above are classical; see L. Lovász, “On the Shannon capacity of a graph,” IEEE Trans. Inform. Theory 25 (1979), 1–7.