Constructing sparse Davenport-Schinzel sequences

DOI10.1016/j.disc.2020.111888zbMath1440.05006arXiv1810.07175OpenAlexW3011816441MaRDI QIDQ2182209

Jesse T. Geneson

Publication date: 21 May 2020

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

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

zbMATH Keywords

pattern avoidance0-1 matriceshypergraph coloringDavenport-Schinzel sequences

Mathematics Subject Classification ID

Hypergraphs (05C65) Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15)

Related Items (2)

Almost all permutation matrices have bounded saturation functions ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounding sequence extremal functions with formations
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
• A relationship between generalized Davenport-Schinzel sequences and interval chains
• 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
• The Number of Edges in $k$-Quasi-planar Graphs
• A Combinatorial Problem Connected with Differential Equations
• Some properties of Davenport-Schinzel sequences
• On a problem of K. Zarankiewicz

This page was built for publication: Constructing sparse Davenport-Schinzel sequences