Paperlane

no. 14 · Friday 13 November 2026

Low-degree colorings without non-essential arguments

Denis S. Krotov

math.CO · v2

Abstract

For the Hamming graph $H(n,q)$, where $q$ is a constant prime power and $n$ grows, we construct perfect colorings without non-essential arguments such that $n$ depends exponentially on the off-diagonal part of the quotient matrix. In particular, we construct unbalanced functions (in the case $q=2$, Boolean functions) such that the number of essential arguments depends exponentially on the degree of the function. Another framing of the main construction is that it gives a sequence of very regular functions (perfect colorings) whose number of essential arguments grows exponentially with respect to sensitivity. A classical result that connects sensitivity with the number of essential arguments in the binary ($q=2$) case is the Simon–Wegener theorem. We prove an analog of this theorem for an arbitrary $q$. Keywords: boolean functions, perfect colorings, equitable partitions, degree, sensitivity, essential arguments

comments
v2: revised; Section 3 added; more general corollaries in Section 2
fields
Combinatorics
pdf ↗ page arXiv:2412.04461 ↗