Let G) be a graph and let S⊆ V(G) be a sensor set with |S|=s. Write operatornameObs(G,W) for the vertices observed from W, and let E(G,S,q) be the expected value polynomial associated with G, S, and q. For the parameters alpha_s,ell(k,i), define alpha_s,ell(k,i):=binoms-ik-i-∑_j=i+1^ellalpha_s,ell(k,j)binoms-ij-i. Degree-bounded expected value polynomial conjecture. The polynomial E(G,S,q) has degree at most ell if and only if, for every 1≤ k≤ s, ∑_W∈ binomSk|operatornameObs(G,W)|=∑_i=1^ellalpha_s,ell(k,i)∑_W∈ binomSi|operatornameObs(G,W)|. This conjecture characterizes the loss of degrees of freedom caused by restricting the expected value polynomial to degree at most ell. The case ell=1 is the previously established linear characterization; the reverse implication is proved in the source, while the forward implication is proved for ell=2 only for many graphs, so the general equivalence remains open.

Degree-bounded expected value polynomial conjecture for fragile power domination

From papers

Let $G$ ) be a graph and let $S\subseteq V(G)$ be a sensor set with $|S|=s$ . Write $\operatorname{Obs}(G,W)$ for the vertices observed from $W$ , and let $\mathcal{E}(G,S,q)$ be the expected value polynomial associated with $G$ , $S$ , and $q$ . For the parameters $\alpha_{s,\ell}(k,i)$ , define

\alpha_{s,\ell}(k,i):=\binom{s-i}{k-i}-\sum_{j=i+1}^{\ell}\alpha_{s,\ell}(k,j)\binom{s-i}{j-i}.

Degree-bounded expected value polynomial conjecture. The polynomial $\mathcal{E}(G,S,q)$ has degree at most $\ell$ if and only if, for every $1\leq k\leq s$ ,

\sum_{W\in \binom{S}{k}}|\operatorname{Obs}(G,W)|=\sum_{i=1}^{\ell}\alpha_{s,\ell}(k,i)\sum_{W\in \binom{S}{i}}|\operatorname{Obs}(G,W)|.

This conjecture characterizes the loss of degrees of freedom caused by restricting the expected value polynomial to degree at most $\ell$ . The case $\ell=1$ is the previously established linear characterization; the reverse implication is proved in the source, while the forward implication is proved for $\ell=2$ only for many graphs, so the general equivalence remains open.

Progress summary

Partially solved

The conjecture has one direction proved in general and some special cases of the other, but the full statement remains open.

A 2025 preprint on fragile power domination formulates this conjecture, asserting an equivalence between a degree bound for the expected-value polynomial and recursive observation-count identities. It records the linear case as already settled but leaves the general equivalence open.

Known results

The reverse implication is proved for every admissible degree $\ell$ (2025 preprint, Theorem 3.6).
The case $\ell=1$ is the established linear characterization (Theorem 3.3).
The forward implication is proved for $\ell=2$ only for many graphs, under an additional lower-coefficient condition (Theorem 3.7).

2025 proposed extension

The authors suggest that their method may extend to arbitrary $\ell$ under analogous coefficient bounds, but explicitly do not claim this proves the conjecture in full. No counterexample, complete proof, or subsequent verification was found.

Current status (as of August 2026): The reverse implication is settled for all $\ell$ , and the forward implication is settled for $\ell=1$ plus restricted $\ell=2$ cases; the general equivalence remains open.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

Beth Bjorkman, Sean English, Johnathan Koch and Amanda Verga, “On Fragile Power Domination”, arXiv:2507.14620 (2025).

1 week ago

We prove a stronger statement for an arbitrary function w:2^S→K on a finite set S of size s, where K has characteristic zero and w(∅)=0. Write A_k=Σ_{W⊆S, |W|=k} w(W), B_k(q)=q^{s-k}(1−q)^k, E(q)=Σ_{k=1}^s A_k B_k(q). Fix 1≤ℓ≤s and use exactly the source's recursively defined coefficients α(k,i)=C(s−i,k−i)−Σ_{j=i+1}^ℓ C(s−i,j−i)α(k,j), 1≤i≤ℓ, with out-of-range binomial coefficients zero.

The polynomials B_0,…,B_s are a basis because they have distinct orders 0,…,s of vanishing at q=1. Hence B_1,…,B_s form a basis for all polynomials of degree at most s vanishing at 1. Define C_i(q)=Σ_{k=1}^s α(k,i)B_k(q). The binomial theorem and the defining recursion give C_i(q)=(1−q)^i−Σ_{j=i+1}^ℓ C(s−i,j−i)C_j(q). Descending induction therefore gives C_i∈V_ℓ, where V_ℓ={F∈K[q]: deg F≤ℓ and F(1)=0}. Moreover, descending induction in the same coefficient recursion proves α(k,i)=δ_{ki} for every 1≤k,i≤ℓ: for i>k all terms vanish, for i=k the value is 1, and for i<k the sole nonzero subsequent term cancels the initial binomial coefficient.

Thus the first ℓ Bernstein-basis coordinates of C_1,…,C_ℓ form the identity matrix. Since dim V_ℓ=ℓ, these polynomials are a basis of V_ℓ. If deg E≤ℓ, then E(1)=0 and therefore E(q)=Σ_{i=1}^ℓ c_i C_i(q). Comparing the first ℓ Bernstein coordinates gives c_i=A_i. Comparing every Bernstein coordinate now gives A_k=Σ_{i=1}^ℓ α(k,i)A_i for all 1≤k≤s, which is precisely the previously missing implication. Conversely, these identities give E=Σ_{i=1}^ℓ A_i C_i∈V_ℓ and hence deg E≤ℓ.

Finally choose w(W)=|Obs(G;W)|. Since Obs(G;∅)=∅, all hypotheses hold, and the equivalence proves the conjecture for every graph, sensor placement, and admissible degree ℓ; indeed no graph-specific assumption is needed.

0 endorsements

Shivam Patel · 21 hours ago