Density and separation for augmented Zarankiewicz numbers
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.16555
curl -X POST /api/v1/records/arxiv/2609.16555/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.16555/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'