{"id":"arxiv/2609.16555","url":"https://arxiv.org/abs/2609.16555","tags":["math.CO"],"score":0,"title":"Density and separation for augmented Zarankiewicz numbers","domain":"math.CO","source":"arxiv","authors":["Nikita Lebedev"],"reviews":0,"subject":"math.CO","summary":"We study the augmented Zarankiewicz problem, in which disjoint pairs of cells are added to a binary matrix with no all-one $2\\times2$ submatrix. The pairs must satisfy compatibility conditions, and the objective counts each original occupied cell and each added pair once. We show that starting with a maximum $C_4$-free matrix can lower the final optimum, answering a question of Qi, Cui, and Xu. Let ${z_A}(m,n)$ be the optimum over all $C_4$-free initial matrices, and ${z_L}(m,n)$ the optimum when the initial matrix must have the maximum number of occupied cells. As $n\\to\\infty$ with $n\\le…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}