2023/03/29 by Dhruv Mubayi, Mubayi, Dhruv, Andrew Suk +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2303.16995
openalex publication_date 2023/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One formulation of the Erdos-Szekeres monotone subsequence theorem states that for any red/blue coloring of the edge set of the complete graph on \1, 2, …, N\, there exists a monochromatic red s-clique or a monochromatic blue increasing path Pn with n vertices, provided N >(s-1)(n-1). %We had previously shown that a suitable generalization of this problem to quadruple systems is essentially equivalent to classical diagonal hypergraph Ramsey numbers. Here, we prove a similar statement as above in the off-diagonal case for triple systems, with the quasipolynomial bound N>2^c(log n)s-1. For the tth power Pnt of the ordered increasing graph path with n vertices, we prove a near linear bound c n(log n)s-2 which improves the previous bound that applied to a more general class of graphs than Pnt due to Conlon-Fox-Lee-Sudakov.