Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences

Keywords

Combinatorics, Subsequence, Upper and lower bounds, Mathematics, Function (biology)

References

• Some properties of Davenport-Schinzel sequencesDavid P. Roselle, Richard Stanton — 1971
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemesHaskell V. Hart — 1986

Cited by

• Two results on a partial ordering of finite sequencesMartin Klazar — 1993
• Enumerating Davenport-Schinzel sequencesDanièle Gardy, Dominique Gouyou-Beauchamps — 1992
• An optimal algorithm for the (≤ k)-levels, with applications to separation and transversal problemsHazel Everett, Jean–Marc Robert, Marc van Kreveld — 1993
• Maximin location of convex objects in a polygon and related dynamic Voronoi diagramsKeiko Imai, Hiroshi Imai, Takeshi Tokuyama — 1990
• Depth, crossings and conflicts in discrete geometryMarek Sulovský — 2011
• New combinatorial techniques for nonlinear ordersAdam W. Marcus — 2008
• Arrangements and their applications in robotics: recent developmentsDan Halperin, Micha Sharir — 1995
• Computing a Largest Empty Anchored Cylinder, and Related ProblemsFrank Follert, Elmar Schömer, Jürgen Sellen — 1995
• Fat triangles determine linearly many holes (computational geometry)J Matousek, Nathaniel Miller, János Pach — 1991
• On critical orientations in the kedem-sharir motion planning algorithmKlara Kedem, Micha Sharir, Sivan Toledo — 1997
• Improved bounds on maximum sets of letters in sequences with forbidden alternationsJesse Geneson — 2013
• Complexity of a Single Face in an Arrangement of s-Intersecting CurvesBoris Aronov, Dmitriy Drusvyatskiy — 2011
• Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizationsGabriel Nivasch — 2008
• A Relationship Between Generalized Davenport-Schinzel Sequences and Interval ChainsJesse Geneson — 2015
• Bounds on extremal functions of forbidden patternsJesse Geneson — 2015
• Obfuscated Drawings of Planar GraphsMihyun Kang, Oleg Pikhurko, Alexander Ravsky — 2008
• Sequences of formation width 4 and alternation length 5Jesse Geneson, Peter M. Tian — 2015
• Almost tight upper bounds for the single cell and zone problems in three dimensionsDan Halperin, Micha Sharir — 1994
• Extremal functions for sequencesMartin Klazar — 1996
• Extremal problems for ordered (hyper)graphs: applications of Davenport-Schinzel sequencesMartin Klazar — 2003

Related papers

• Summability of Subsequences and Rearrangements of SequencesThomas A. Keagy — 1978
• Uniform subsequential estimates on weakly null sequencesM. Brixey, Ryan M. Causey, Patrick Frankart — 2019
• Subsequence principles for vector-valued random variablesD. J. H. Garling — 1979
• Regular methods of summability and the Banach-Saks property for double sequences‎Raluca Dumitru, Jose A‎. ‎Franco, Richard F. Patterson — 2021
• Weakly null sequences with upper estimatesDaniel Freeman — 2007
• A bounded sequence of normal functionals has a subsequence which is nearly weakly convergentJames K. Brooks, Kazuyuki Saitô, J. D. Maitland Wright — 2002
• An upper bound for the solving degree in terms of the degree of regularityFlavio Salizzoni — 2023
• Lower Bounds on the Complexity of 0-1-Valued Recursive FunctionsTsun S. Chow — 1976