Concept icon
Concept

Bounding the number of wires used to name low-degree incidence monomials

For one degree array, its wire count M=sum_gh ceil(log2 C_gh) is at most J^2+log2(product C_gh). Each combination of subsets names a distinct squarefree monomial of degree at most K. Its count is at most binom(N+K,K): nonnegative exponent vectors of total at most K inject into solutions of sum of N+1 exponents=K by adding slack, counted by stars and bars. The standard bound binom(N+K,K)<=(e(N+K)/K)^K gives M<=J^2+K log2(e(N+K)/K)=O_(k,c)(n nu), since K=Theta_(k,c)(n) and N<=n lambda^{O_(k,c)(1)}. Also ceil(log2 C_gh)<=N_gh, bounding each vertex degree by its group incidence count.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math