2026/07/17 by Gregory Gutin, Yiming Hao, Yacong Zhou · 1 citation
#math.CO #cs.DM
Let G=(V,E) be a finite simple graph of order n≥ 1, and let ℓ:V→\0,1\ be a prescribed parity labeling. A set S⊆ V is called ℓ-admissible if dS(v)≡ ℓ(v)\pmod 2 for every v∈ S, where dS(v)=|NG(v)∩ S|. Let h_ℓ(G) be the maximum order of an ℓ-admissible set and let f\rm oe(G)=min_ℓ h_ℓ(G). For x∈\mathbb R, define the weighted counting polynomial Mℓ,x(G)=∑_S∈ \cal A_ℓ(G)x|S|, where \cal A_ℓ(G) is the collection of all ℓ-admissible sets in G. For R⊆ V, let z_ℓ(R) be the number of vertices v∈ V∖ R for which dR(v)≡ℓ(v)\pmod 2. We prove the exact identity Mℓ,x(G) =2-n∑R⊆ V x|R|(2+x)z_ℓ(R)(2-x)n-z_ℓ(R)-|R|. If G has no isolated vertices, then, for every ℓ and every x∈(0,2), Mℓ,x(G)>xn/2(4-x2)n/4. Combining this estimate with a binary-entropy upper bound and optimizing x gives f\rm oe(G)>c_*n>(2n)/(21), where c_*≈0.095862615. Ferber and Krivelevich (Adv. Math. 2022) proved that h1(G)≥ 10-4n, where 1 is the all-one labeling. Since h1(G)≥ f\rm oe(G), our result improves coefficient in their bound by almost three orders of magnitude, and does so simultaneously for every labeling.