Sharp bounds on Davenport-Schinzel sequences of every order

DOI10.1145/2794075zbMATH Open1426.68232OpenAlexW2570341361MaRDI QIDQ3177745FDOQ3177745

Authors: Seth Pettie 

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2794075

Recommendations

• Sharp bounds on Davenport-Schinzel sequences of every order
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations

zbMATH Keywords

combinatoricssequencesforbidden patterns

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorics on words (68R15)

Cited In (8)

• Title not available (Why is that?)
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constructing sparse Davenport-Schinzel sequences
• Sequence saturation

This page was built for publication: Sharp bounds on Davenport-Schinzel sequences of every order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177745)