We study the augmented Zarankiewicz problem, in which disjoint pairs of cells are added to a binary matrix with no all-one 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 -free matrix can lower the final optimum, answering a question of Qi, Cui, and Xu. Let be the optimum over all -free initial matrices, and the optimum when the initial matrix must have the maximum number of occupied cells. As with , we prove and determine the sharp second-order term: An explicit construction gives a separation at . We also find a sharp density threshold: when and , the limited density tends to if and only if . The proofs combine density and stability estimates, combinatorial constructions, and an exact polynomial certificate.

生成讲解博客的中文版本

生成AI智能校验的中文版本