On the Extremal Functions of Acyclic Forbidden 0-1 Matrices

Pettie, Seth and Tardos, Gábor (2024) On the Extremal Functions of Acyclic Forbidden 0-1 Matrices. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia (PA), pp. 1166-1176. ISBN 9781611977912

Preview

Text 1.9781611977912.45.pdf Download (572kB) | Preview

Abstract

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, 1unˆn whose submatrices avoid a fixed pattern P P t0, 1ukˆl. This theory has been wildly successful at resolving problems in combinatorics [Kla00, MT04, CK12], discrete and computational geometry [F¨ur90, 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, CPY24]. 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¨uredi and Hajnal [FH92]. At the two extremes, it is consistent with prior results that @P. ExpP, nq ď n log1`op1q n, and also consistent that @ϵ ą 0.DP. ExpP, nq ě n2´ϵ. In this paper we establish a stronger lower bound on the extremal functions of acyclic P . Specifically, for any t ě 1 we give a new construction of relatively dense 0–1 matrices with Θpnplog n{ log log nqtq 1s that avoid a certain acyclic pattern Xt. 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.

Actions (login required)

Edit Item