27 problems

Let $K_m^3=K_m\square K_m\square K_m$ be the 3-dimensional $m$-ary Hamming cube, and let $\gamma^{ID}(G)$ denote the minimum size of an identifying code in a graph $G$. Goddard–Was…

Let $H(n,q,d)$ be the Hamming graph, and let $K_d(1)$ denote the relevant Krawtchouk eigenvalue. Van Dam–Sotirov's conjecture. For $d \ge \frac{(q-1)n+1}{q}$, with $d$ even when…

Let $H(n,j)$ be the distance-$j$ binary Hamming graph with vertex set $\mathbb{Z}_2^n$, in which two vectors are adjacent exactly when their Hamming distance is $j$. For the binary…

Asymptotic tightness conjecture. For any fixed positive integer $d$, we have

Let $H_n$ be a Hamming graph, expressed as a Cartesian product of complete graphs, and let $c(H_n)$ and $p(H_n)$ denote its Carathéodory number and the upper bound obtained in the…

Let $K_n\square K_m$ be the Cartesian product of complete graphs, with $n\ge 3$, $m\ge n+1$, and $3\le k\le 2n$. The weak $k$-metric dimension formula asserts that … This conjectur…

Let $H(d,3)$ be the Hamming graph on length-$d$ words over an alphabet of size $3$, and let $\Phi_d(H(d,3))$ be the associated system of polynomials. A solution is all-nonzero if e…

Let $m$ be a positive integer, let $\varepsilon$ be an $m$-th primitive root of unity, and let $H(n,m)$ be the Hamming graph. Write $H_1,\dots,H_m$ for possibly empty induced subgr…

Let $m$ be a positive integer, let $\varepsilon$ be an $m$-th root of unity, and let $H(n,m)$ be the Hamming graph on $\mathcal U_m^{\,n}$. For each $k$, let $H_{\varepsilon^k}$ be…

Let $H(n,q)$ denote the $q$-ary Hamming graph, and let $b(H(n,q))$ denote its bipartite independence-related parameter as defined in the paper. Fix an integer $q\geq 3$. Sharp-boun…

Let $\square_{i=1}^n K_k$ be the Cartesian product of $n$ copies of the complete graph $K_k$, and let $p_c(G,r)$ denote the critical probability for $r$-neighbor bootstrap percolat…

Ansensio–García-Marco–Knauer conjecture. All such subsets satisfy

Let $q=p^b$ for a prime $p$, and let $H(q,d)$ denote the Hamming graph with alphabet size $q$ and dimension $d$. An efficient $(1,k)$-dominating function is a function of the type…

Hamming distinct-eigenvalue conjecture. If $H(d,q,j)$ is connected, it has more than $d/2$ distinct eigenvalues.

For fixed parameters $q$, $b$, and $c$, call $(q,b,c)$ admissible if there is an integer $n_0=n_0(b,c;q)$ such that a $(b,c)$-coloring of $H(n,q)$ exists if and only if $n\geq n_0$…

Let $f: \{0,\ldots,q-1\}^n \rightarrow \{0,1\}$ be a function with $B$ zeros and $C$ ones, where $q\geq 3$. Suppose that for some $k$, every $k$-face has the same number … of ones…

Generalized correlation-immunity bound. If there exists a $(b,c)$-coloring in $H(n,q)$ with $b'+c'>q$, then

Let $H(n,q)$ be the Hamming graph, and let a $\lambda$-fold $1$-packing be a code whose radius-$1$ balls cover each vertex at most $\lambda$ times. Proposition establishes that dis…

Let $H_q(n,d)$ be the Hamming-distance graph whose vertices are ${\mathbb Z}_q^n$, with two vertices adjacent when their Hamming distance is at least $d$. A $q^{n-d+1}$-coloring is…

Largest-Laplacian-eigenvalue conjecture. If $q\geq 2$ and $j\geq d-\frac{d-1}{q}$, with $j$ even if $q=2$, then $\lambda$ is the largest Laplacian eigenvalue of $H(d,q,j)$. This co…

Let $C$ be a completely regular code in a Hamming graph, and let its covering radius be the maximum distance from a vertex of the Hamming graph to $C$. Leonard conjecture. All comp…

Mean-field behaviour conjecture. The barely supercritical regime for $H(2,n)$ should have similar behaviour to that of the Erdős–Rényi random graph $G(n,p)$.

Sharp second-component asymptotic conjecture. The second largest component should satisfy

Second-component scale conjecture. The second largest component should satisfy

Giant-component conjecture. Following van der Hofstad and Łuczak, the largest component should satisfy