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

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.

References

Primary source

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

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-written argument claims a complete proof for every allowed degree, but it has not been independently verified and the published source records only partial results.

Bjorkman, English, Koch, and Verga formulate the conjecture in their 2025 preprint on fragile power domination: a degree bound on the expected-value polynomial is equivalent to recursive identities among observation counts.

Known results

The case $\ell=1$ is characterized completely (Theorem 3.3).
The implication from the recursive identities to degree at most $\ell$ is proved for every admissible $\ell$ (Theorem 3.6).
The converse is proved for $\ell=2$ only for many graphs satisfying an additional coefficient condition (Theorem 3.7).
The authors state that the general equivalence remains unproved.

Posted attempt

An unverified argument claims a stronger algebraic statement for arbitrary set functions, using the Bernstein-basis polynomials $q^{s-k}(1-q)^k$ , and concludes the conjecture for every graph, sensor set, and admissible $\ell$ . It claims a complete proof, but no independent verification is provided.

Current status (as of August 2026): The published source settles the reverse implication for all $\ell$ , the full $\ell=1$ case, and restricted $\ell=2$ cases; a posted argument claims the remaining converse, but that claim is unverified.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

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.