On the Extremal Functions of Acyclic Forbidden 0-1 Matrices

The extremal theory of forbidden 0-1 matrices studies the asymptotic growth of the function ExpP, nq, which is the maximum weight of a matrix A P t0, 1u nˆn whose submatrices avoid a fixed pattern P P t0, 1u kˆl . This theory has been wildly successful at resolving problems in combinatorics [Kla00, MT04, CK12], discrete and computational geometry [Für90, Agg15, ES96, PS91, Mit92, BG91], structural graph theory [GM14, BGK 21, BKTW22] and the analysis of data structures [Pet10, KS20], particularly corollaries of the dynamic optimality conjecture [CGK 15b, CGK 15a, CGJ 23].

All these applications use acyclic patterns, meaning that when P is regarded as the adjacency matrix of a bipartite graph, the graph is acyclic. The biggest open problem in this area is to bound ExpP, nq for acyclic P . Prior results [Pet11a, PS13] have only ruled out the strict Opn log nq bound conjectured by Füredi and Hajnal [FH92]. It is consistent with prior results that @P. ExpP, nq ď n log 1`op1q n, and also consistent that @ǫ ą 0.DP. ExpP, nq ě n 2´ǫ .

In this paper we establish a stronger lower bound on the extremal functions of acyclic P . Specifically, we give a new construction of relatively dense 0-1 matrices with Θpnplog n log log nq t q 1s that avoid an acyclic X t . Pach and Tardos [PT06] have conjectured that this type of result is the best possible, i.e., no acyclic P exists for which ExpP, nq ě nplog nq ωp1q .