Sharp thresholds for a phase transition related to weakly increasing sequences

DOI10.1093/LOGCOM/EXQ004MaRDI QIDQ2882557zbMATH OpenOpenAlexFDO

Authors Michiel De Smet, Andreas Weiermann

Publication date 7 May 2012

Published in Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/exq004

zbMATH Keywords

Ackermann functionErdős-Szekeres theoremphase transitionsRamsey theory

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Review text

In the paper the recursion-theoretic complexity of certain assertions related to the Erdős-Szekeres theorem are investigated. It is shown that resulting density principles give rise to Ackermannian growth. These assertions are then parametrized with respect to a number-theoretic function \(f\). It is investigated for which functions \(f\) Ackermannian growth is still preserved.

Recommendations

• Phase Transitions for Weakly Increasing Sequences
• Phase transitions related to the pigeonhole principle
• Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers
• Erdős-Szekeres theorem for multidimensional arrays
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1

Cited in

(4)

• Phase transition thresholds for some Friedman-style independence results
• Phase Transitions for Weakly Increasing Sequences
• Primitive recursion and the chain antichain principle
• Phase transitions related to the pigeonhole principle

This page was built for publication: Sharp thresholds for a phase transition related to weakly increasing sequences

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