Abstract:For two vectors $x,y\in [b]^k$, consider the bipartite graph with two copies of $[b]$ in which $i$ on the left is joined to $j$ on the right if $(x_t,y_t)=(i,j)$ for some coordinate $t$. We study the largest size of a family $C\subseteq [b]^k$ such that, for every two distinct $x,y\in C$, this bipartite graph contains a cycle.
We give a natural construction for such families and conjecture that it is optimal whenever $k$ is large relative to $b$. We prove an LYM-type upper bound that is asymptotically tight with respect to this construction, and is exact when $k$ is large and divisible by $b$. We then refine the argument using a circular ordering, obtaining the sharp full-support bound when $k\equiv -1\pmod b$. In the case $b=3$, we prove the exact general result when $k\equiv -1\pmod 3$ and $k$ is sufficiently large. The problem is motivated by the Daniely--Shalev-Shwartz dimension and the pseudocube formulation of a higher-alphabet Sauer-Shelah-Perles lemma.
From: Varun Sivashankar [view email]
[v1]
Tue, 23 Jun 2026 18:11:17 UTC (16 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。