Premium
THE ERDŐS–SZEKERES PROBLEM AND AN INDUCED RAMSEY QUESTION
Author(s) -
Mubayi Dhruv,
Suk Andrew
Publication year - 2019
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579319000135
Subject(s) - mathematics , hypergraph , combinatorics , conjecture , ramsey's theorem , integer (computer science) , regular polygon , set (abstract data type) , polytope , discrete mathematics , ramsey theory , graph , geometry , computer science , programming language
Motivated by the Erdős–Szekeres convex polytope conjecture in R d , we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers n > k ⩾ 5 , what is the minimum integerg k ( n )such that any k ‐uniform hypergraph ong k ( n )vertices with the property that any set of k + 1 vertices induces 0, 2, or 4 edges, contains an independent set of size n . Our main result shows thatg k ( n ) > 2 c n k − 4, where c = c ( k ) .