Sharp bounds on Davenport-Schinzel sequences of every order

DOI10.1145/2794075MaRDI QIDQ3177745zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(9)

• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 7673608 (Why is no real title available?)
• scientific article; zbMATH DE number 1424289 (Why is no real title available?)
• Constructing sparse Davenport-Schinzel sequences
• Sequence saturation
• Sharp bounds on Davenport-Schinzel sequences of every order

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)