{"id":"arxiv/2606.25055","url":"https://arxiv.org/abs/2606.25055","tags":["math.CO"],"score":0,"title":"Pseudoshattering Pairs","domain":"math.CO","source":"arxiv","authors":["Noga Alon","Varun Sivashankar"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-23","reactions":{}}