Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations

MaRDI QIDQ4633804zbMATH OpenFDO

Authors Gabriel Nivasch

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496771

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Combinatorics on words (68R15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• 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
• Sharp bounds on Davenport-Schinzel sequences of every order
• Improved lower bounds on the length of Davenport-Schinzel sequences

Cited in

(13)

• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• Improved lower bounds on the length of Davenport-Schinzel sequences
• A simplified construction of nonlinear Davenport-Schinzel sequences
• Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
• Upper bounds for stabbing simplices by a line
• A relationship between generalized Davenport-Schinzel sequences and interval chains
• scientific article; zbMATH DE number 1808181 (Why is no real title available?)
• Sharp bounds on Davenport-Schinzel sequences of every order
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• scientific article; zbMATH DE number 1341912 (Why is no real title available?)
• Sharp bounds on Davenport-Schinzel sequences of every order
• scientific article; zbMATH DE number 7673608 (Why is no real title available?)
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences

This page was built for publication: Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations

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