2022/03/03 by Jeremy Tan, Tan, Jeremy · 1 citation
Computer Science · Mathematics · #05C35 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #Matrix Theory and Algorithms #Polynomial and algebraic computation #Tensor decomposition and applications #cs.DM #cs.LO #math.CO #msc:05C35
paper · pdf · doi:10.48550/arxiv.2203.02283
24 pages, 2 figures. Added correctness proof of partition-generating algorithm and a new subsection on coverings
openalex publication_date 2022/03/03 · arxiv created 2022/04/19 · arxiv updated 2022/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Zarankiewicz function gives, for a chosen matrix and minor size, the maximum number of ones in a binary matrix not containing an all-one minor. Tables of this function for small arguments have been compiled, but errors are known in them. We both correct the errors and extend these tables in the case of square minors by expressing the problem of finding the value at a specific point as a series of Boolean satisfiability problems, exploiting permutation symmetries for a significant reduction in the work needed. When the ambient matrix is also square we also give all non-isomorphic examples of matrices attaining the maximum, up to the aforementioned symmetries; it is found that most maximal matrices have some form of symmetry.