Almost-all-graphs unimodality conjecture for upward monotone augmented graph properties

An upward-monotone augmented graph property that is almost never unimodal

Status: DISPROVED. The argument below disproves Conjecture 1 of Johann A. Makowsky and Vsevolod Rakita, arXiv:2102.00268v4, published in European Journal of Combinatorics 108 (2023), article 103637, doi:10.1016/j.ejc.2022.103637.

The conjecture says that every upward-monotone augmented graph property has a unimodal counting sequence for almost every labelled graph. Here an augmented property is a class of pairs $(G,S)$, where $G$ is a finite simple undirected graph and $S\subseteq V(G)$, invariant under graph isomorphisms that carry the distinguished set along. Upward monotonicity means that enlarging $S$, with $G$ fixed, preserves membership. “Almost every” means that the probability tends to one in $G(n,1/2)$.

The construction uses two ways for a set to qualify. A set may contain a distinguished, isomorphism-invariant group of vertices, or it may simply be sufficiently large. The first condition gives a shifted binomial sequence. The second turns on after this sequence has started decreasing, causing a strict upward jump.

The property

For a finite simple graph $G$, let

$$O(G)=\{v\in V(G):\deg_G(v)\text{ is odd}\},\qquad r=|O(G)|,\qquad m=|V(G)|-r,$$

and put $q=\lfloor m/2\rfloor$ and $t=r+q+3$. Define one property $\mathcal P$, for graphs of every order, by

$$(G,S)\in\mathcal P \quad\Longleftrightarrow\quad O(G)\subseteq S\ \text{ or }\ |S|\ge t. \tag{1}$$

This definition also applies when $t>|V(G)|$; in that case its second condition is never satisfied. Degrees, their parities, and all the cardinalities in (1) are preserved by graph isomorphisms. Thus $\mathcal P$ is an augmented graph property. Each of the two conditions in (1) is preserved on enlarging $S$, so $\mathcal P$ is upward monotone.

Let $c_k(G)$ count the qualifying $k$-subsets. With the convention that an out-of-range binomial coefficient is zero, direct counting gives

$$c_k(G)= \begin{cases} \displaystyle\binom{m}{k-r},&k<t,\\[4pt] \displaystyle\binom{m+r}{k},&k\ge t. \end{cases} \tag{2}$$

Indeed, below the threshold one must take all $r$ odd-degree vertices and choose the remaining $k-r$ vertices from the other $m$. At or above the threshold every set qualifies.

A strict dip

Suppose that $r\ge1$ and $m\ge24$. The three consecutive indices $t-2,t-1,t$ lie between zero and $m+r$. Equation (2) gives

$$c_{t-2}=\binom{m}{q+1},\qquad c_{t-1}=\binom{m}{q+2},\qquad c_t=\binom{m+r}{r+q+3}. \tag{3}$$

First,

$$\frac{\binom{m}{q+2}}{\binom{m}{q+1}} =\frac{m-q-1}{q+2}<1, \tag{4}$$

both for $m=2q$ and for $m=2q+1$. Hence $c_{t-2}>c_{t-1}$.

For the other inequality put $s=m-q-3$. Since $r\ge1$,

$$c_t=\binom{m+r}{s}\ge\binom{m+1}{s}, \qquad c_{t-1}=\binom{m}{s+1}.$$

Their lower-bound ratio is

$$\frac{\binom{m+1}{s}}{\binom{m}{s+1}} =\frac{(m+1)(s+1)}{(m+1-s)(m-s)}. \tag{5}$$

If $m=2q$, the numerator in (5) exceeds the denominator by $q^2-10q-14$. If $m=2q+1$, the difference is $q^2-7q-14$. Here $m\ge24$ implies $q\ge12$, and both differences are strictly positive. Thus

$$c_{t-2}>c_{t-1}<c_t. \tag{6}$$

A sequence with a strict decrease followed by a strict increase cannot be unimodal.

Why the dip occurs for almost every graph

For $n\ge1$ and $G\sim G(n,1/2)$, the vector of degree parities is uniform among the $2^{n-1}$ binary vectors with even coordinate sum. Here is a direct proof. Fix the edges among the first $n-1$ vertices. For each $i<n$, the edge $\{i,n\}$ independently determines whether the already fixed parity at vertex $i$ is toggled. Thus the first $n-1$ final parities are independent fair bits. The last parity is determined by the handshaking identity, because the number of odd-degree vertices is even.

Consequently, for every even $r$,

$$\Pr(|O(G)|=r)=2^{1-n}\binom nr, \tag{7}$$

and the probability is zero for odd $r$. The exceptional event $r=0$ or $m<24$ therefore has probability at most

$$2^{1-n}\left(1+\sum_{j=0}^{23}\binom nj\right), \tag{8}$$

which tends to zero. Outside that event, (6) proves non-unimodality. In fact this fixed property satisfies the stronger conclusion

$$\lim_{n\to\infty} \Pr\bigl((c_0(G),\ldots,c_n(G))\text{ is unimodal}\bigr)=0.$$

This contradicts Conjecture 1.

A small explicit example

Take the path $P_{15}$ on vertices $1,\ldots,15$, with edges $\{i,i+1\}$ for $1\le i<15$. Its only odd-degree vertices are its two endpoints, so $r=2$, $m=13$, and $t=11$. Equation (2) gives

$$c_9=\binom{13}{7}=1716, \qquad c_{10}=\binom{13}{8}=1287, \qquad c_{11}=\binom{15}{11}=1365.$$

Thus even this connected graph exhibits the strict dip $1716>1287<1365$. The random-graph argument, rather than this single finite example alone, supplies the disproof of the almost-everywhere assertion.

The counterexample does not contradict the same paper's Theorem 1.13, which applies to counting induced subgraphs in a fixed nontrivial co-hereditary graph class. It shows that monotonicity in the distinguished set, without that additional structural restriction, is insufficient.