×

The Erdős-Szekeres problem and an induced Ramsey question. (English) Zbl 1411.05255

Summary: Motivated by the Erdős-Szekeres convex polytope conjecture in \(\mathbb{R}^{d}\), we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers \(n>k\geqslant 5\), what is the minimum integer \(g_{k}(n)\) such that any \(k\)-uniform hypergraph on \(g_{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 that \(g_{k}(n)>2^{cn^{k-4}}\), where \(c=c(k)\).

MSC:

05D10 Ramsey theory
52C99 Discrete geometry
05C65 Hypergraphs
05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Erdős, P. and Szekeres, G., A combinatorial problem in geometry. Compos. Math.21935, 463-470. · JFM 61.0651.04
[2] Erdős, P. and Szekeres, G., On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest. Eötvös Sect. Math.3-41960-61, 53-62. · Zbl 0103.15502
[3] Károlyi, G., Ramsey-remainder for convex sets and the Erdős-Szekeres theorem, Discrete Appl. Math., 109, 163-175, (2001) · Zbl 0974.52014
[4] Károlyi, G. and Valtr, P., Point configurations in d-space without large subsets in convex position. Discrete Comput. Geom.302003, 277-286. · Zbl 1051.52012
[5] Matoušek, J., Lectures in Discrete Geometry, (2002), Springer · Zbl 0999.52006
[6] Motzkin, T., Cooperative classes of finite sets in one and more dimensions, J. Combin. Theory, 3, 244-251, (1967) · Zbl 0203.01403
[7] Szekeres, G. and Peters, L., Computer solution to the 17-point Erdős-Szekeres problem. ANZIAM J.482006, 151-164. · Zbl 1152.52008
[8] Suk, A., On the Erdős-Szekeres convex polygon problem, J. Amer. Math. Soc., 30, 1047-1053, (2017) · Zbl 1370.52032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.