Phase Transitions for Weakly Increasing Sequences

DOI10.1007/978-3-540-69407-6_20MaRDI QIDQ3507431zbMATH OpenOpenAlexFDO

Authors Michiel De Smet, Andreas Weiermann

Publication date 19 June 2008

Published in Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69407-6_20

zbMATH Keywords

Ackermann functionDilworthErdös-Szekeresphase transitionsRamsey theoryweakly increasing sequences

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• Sharp thresholds for a phase transition related to weakly increasing sequences
• Phase transitions related to the pigeonhole principle
• Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers
• Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1

Cites work

• An extremely sharp phase transition threshold for the slow growing hierarchy
• Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results
• Classifying the phase transition threshold for Ackermannian functions
• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• On the strength of Ramsey's theorem for pairs
• Phase transition thresholds for some Friedman-style independence results
• Reverse mathematics and the equivalence of definitions for well and better quasi-orders
• Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers
• Some independence results for Peano arithmetic
• The strength of infinitary Ramseyan principles can be accessed by their densities

Cited in

(5)

• Sharp thresholds for a phase transition related to weakly increasing sequences
• Primitive recursion and the chain antichain principle
• Phase transitions related to the pigeonhole principle
• Logical Approaches to Computational Barriers
• Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers

This page was built for publication: Phase Transitions for Weakly Increasing Sequences

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