Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices

DOI10.1016/j.disc.2018.03.023zbMath1387.05003arXiv1610.09774OpenAlexW2963380013MaRDI QIDQ1752672

Seth Pettie, Julian Wellman

Publication date: 24 May 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.09774

zbMATH Keywords

Zarankiewicz problemforbidden submatrixforbidden subsequenceDavenport-Schinzel problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Related Items (3)

Almost all permutation matrices have bounded saturation functions ⋮ Constructing sparse Davenport-Schinzel sequences ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• New asymptotics for bipartite Turán numbers
• Norm-graphs and bipartite Turán numbers
• Origins of Nonlinearity in Davenport–Schinzel Sequences
• Sharp Bounds on Davenport-Schinzel Sequences of Every Order
• Three Generalizations of Davenport--Schinzel Sequences
• Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
• A Combinatorial Problem Connected with Differential Equations
• The History of Degenerate (Bipartite) Extremal Graph Problems
• On Graphs that do not Contain a Thomsen Graph
• Some properties of Davenport-Schinzel sequences
• On a problem of K. Zarankiewicz

This page was built for publication: Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices