Cochran's multiplier conjecture for generalized action graphs

Cochran's action-graph multiplier conjecture and a complete characterization

Source and version. Sarah Klanderman, Katy McDicken, and Amelia Tebbe, Conditions for Building Generalized Action Graphs From Sequences, The PUMP Journal of Undergraduate Research 9 (2026), 158–179, formulate Cochran's multiplier conjecture as Conjecture 3.3 and explicitly leave its necessity direction open. The earlier arXiv version labels the same assertion Conjecture 5.1. Crucially, the final published Definition 1.1 specifies directed, labeled, rooted trees; the older preprint only says “graphs.” The rooted-tree hypothesis is essential below.

We prove the conjecture and obtain the exact necessary-and-sufficient condition for a positive integer sequence to admit generalized action graphs. In particular, the auxiliary multipliers need only be nonnegative, not strictly positive as assumed in the sufficient direction of the source's Theorem 1.1.

1. The published axioms

Let

$$s_0,s_1,s_2,\ldots\in\mathbb Z_{>0}$$

and let $G_0,G_1,G_2,\ldots$ be a sequence of generalized action graphs in the sense of the published Definition 1.1. Thus:

1. Each $G_n$ is a directed, labeled, rooted tree. The tree $G_0$ has $s_0$ vertices labeled $0$ and no edges, and $G_n$ extends $G_{n-1}$ by adding exactly $s_n$ vertices labeled $n$.
2. For every vertex $v$ of $G_n$, its full descendant subtree is isomorphic, after the appropriate uniform shift of vertex labels, to one of the earlier action graphs $G_j$. The source explains this label-shift convention in Section 3.1 and makes the shift explicit in Theorem 1.1.
3. Every leaf of $G_n$ has label $n$.

Since $G_0$ is a rooted tree with no edges, necessarily

$$s_0=1. \tag{1}$$

Write $\rho$ for the unique vertex labeled $0$, and define

$$z_i = \#\{v:\ v\text{ is a child of }\rho \text{ and has label }i\} \qquad(i\geq1). \tag{2}$$

The quantity $z_i$ is independent of the choice of $G_n$ with $n\geq i$: vertices labeled $i$ first occur in $G_i$, and subsequent graphs extend the existing rooted tree without changing its previous edges.

2. Every root branch has a forced type

Fix $n\geq1$, and let $v$ be any child of $\rho$ whose label is $i$. The descendant subtree rooted at $v$ is, by the second axiom, a copy of some $G_j$ with all labels shifted upward by $i$. The leaves of $G_j$ have label $j$ by the third axiom, so the leaves of this shifted copy have label $i+j$.

Every leaf of a full descendant subtree in a rooted tree is also a leaf of the whole tree. Therefore those same leaves have label $n$ in $G_n$. It follows that

$$i+j=n, \qquad\text{and hence}\qquad \operatorname{Desc}_{G_n}(v) \cong G_{n-i} \quad\text{with all labels shifted by }i. \tag{3}$$

The number of vertices labeled $n-i$ in $G_{n-i}$ is exactly $s_{n-i}$ by the first axiom. Consequently, the branch below each root child labeled $i$ contains precisely

$$s_{n-i} \tag{4}$$

vertices labeled $n$.

Because $G_n$ is a rooted tree, the descendant subtrees of its distinct root children are disjoint, and together they contain every nonroot vertex. In particular, they partition all $s_n$ vertices labeled $n$. Grouping these branches according to the label $i$ of their first vertex gives

$$\boxed{ s_n=\sum_{i=1}^{n}z_i s_{n-i} \qquad(n\geq1). } \tag{5}$$

Since $s_0=1$, the summand with $i=n$ is simply $z_n$. Solving (5) for that summand proves Cochran's exact conjectured formula:

$$\boxed{ z_n=s_n-\sum_{i=1}^{n-1}z_i s_{n-i} \qquad(n\geq1). } \tag{6}$$

The argument uses the final published rooted-tree condition essentially: for a general directed graph, distinct root branches can share descendants, and the counting step (5) would not follow.

3. The complete generating-function classification

Define the formal power series

$$S(x)=\sum_{n\geq0}s_nx^n, \qquad Z(x)=\sum_{n\geq1}z_nx^n. \tag{7}$$

Multiplication of (5) by $x^n$ and summation over $n\geq1$ yields

$$S(x)-1=Z(x)S(x). \tag{8}$$

Since $S(0)=1$, formal inversion is valid, and therefore

$$\boxed{ Z(x)=1-\frac{1}{S(x)}, \qquad S(x)=\frac{1}{1-Z(x)}. } \tag{9}$$

Every $z_n$ counts actual root children, so

$$z_1=s_1>0, \qquad z_n\geq0\quad(n\geq2). \tag{10}$$

We next prove that these necessary conditions are also sufficient.

Suppose $s_0=1$ and that the uniquely determined coefficients of

$$Z(x)=1-\frac{1}{S(x)}=\sum_{i\geq1}z_ix^i \tag{11}$$

satisfy (10). For each $i\geq1$, introduce an alphabet $A_i$ consisting of $z_i$ distinguishable letters, each assigned weight $i$. Alphabets with $z_i=0$ are simply empty. A word

$$w=a_1a_2\cdots a_r, \qquad a_j\in A_{i_j},$$

has weight

$$|w|=i_1+i_2+\cdots+i_r. \tag{12}$$

The empty word $\varnothing$ has weight $0$.

Construct $G_n$ as follows: its vertices are all words of weight at most $n$; the label of a vertex is its weight; its root is the empty word; and its directed edges are

$$w\longrightarrow wa \qquad \bigl(a\in A_i,\ |w|+i\leq n\bigr). \tag{13}$$

Each nonempty word has exactly one parent, obtained by deleting its final letter. Thus $G_n$ is a finite directed rooted tree. The ordinary generating function for all words by weight is

$$\sum_w x^{|w|} = \sum_{r\geq0}Z(x)^r = \frac{1}{1-Z(x)} =S(x). \tag{14}$$

Hence precisely $s_i$ vertices have label $i$, and passing from $G_{n-1}$ to $G_n$ adds exactly the $s_n$ words of weight $n$. This is the first axiom.

For a word $w$ of weight $i$, every descendant has the unique form $wu$, where $u$ is a word of weight at most $n-i$. Deleting the prefix $w$ gives a directed rooted-tree isomorphism

$$\operatorname{Desc}_{G_n}(w) \longrightarrow G_{n-i}, \qquad wu\longmapsto u, \tag{15}$$

and the labels differ by exactly $i$. This is the second axiom.

Finally, $z_1>0$ guarantees the existence of a letter of weight $1$. Every word of weight strictly less than $n$ can therefore be extended by one such letter, while no word of weight $n$ can be extended within $G_n$. Consequently,

$$w\text{ is a leaf of }G_n \quad\Longleftrightarrow\quad |w|=n. \tag{16}$$

This is the third axiom. We have therefore proved the sharp equivalence

$$\boxed{ \begin{aligned} &(s_n)_{n\geq0}\text{ admits generalized action graphs} \\ &\quad\Longleftrightarrow\quad s_0=1,\quad [x]\left(1-\frac1{S(x)}\right)>0, \quad [x^n]\left(1-\frac1{S(x)}\right)\geq0 \quad(n\geq2). \end{aligned} } \tag{17}$$

For the positive sequences considered in the source, the strict inequality for the coefficient of $x$ is automatic because it equals $s_1$.

4. Zero multipliers and structural uniqueness

The source's Theorem 1.1 assumes $z_i>0$ for every $i\geq1$. Condition (17) shows that this is stronger than necessary: a root can have no child with some particular label.

For example, take

$$s_n=1\quad(n\geq0). \tag{18}$$

Then

$$S(x)=\frac1{1-x}, \qquad Z(x)=1-\frac1{S(x)}=x, \tag{19}$$

so

$$z_1=1, \qquad z_i=0\quad(i\geq2). \tag{20}$$

The corresponding action graph $G_n$ is simply the directed path

$$0\longrightarrow1\longrightarrow\cdots\longrightarrow n, \tag{21}$$

which satisfies all three published axioms. Thus zero higher multipliers must be permitted in the complete characterization.

More generally, (3) applies to every vertex, not only root children. Inside the subtree below a vertex labeled $j$, the number of children whose labels are $j+i$ is exactly $z_i$. Therefore every admissible action graph is, up to a rooted label-preserving tree isomorphism, the weighted-word tree (13). The multiplier sequence is uniquely determined by (6), and the entire graph structure is determined by those multipliers.

This proves Cochran's multiplier conjecture, completes the missing necessity direction of the published paper, weakens its sufficiency hypothesis from strict positivity to the optimal nonnegativity condition, and gives the requested complete classification of admissible sequences.