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

zbMATH Open1422.68201MaRDI QIDQ4633804FDOQ4633804

Authors: Gabriel Nivasch 

Publication date: 6 May 2019

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

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

Mathematics Subject Classification ID

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

Cited In (13)

• 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
• Upper bounds for stabbing simplices by a line
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
• A simplified construction of nonlinear Davenport-Schinzel sequences
• Improved lower bounds on the length of Davenport-Schinzel sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sharp bounds on Davenport-Schinzel sequences of every order
• A relationship between generalized Davenport-Schinzel sequences and interval chains
• Sharp bounds on Davenport-Schinzel sequences of every order

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)