𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the generalized Erdös-Szekeres Conjecture — a new upper bound

✍ Scribed by Yair Caro

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
223 KB
Volume
160
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We prove the following result: For every two natural numbers n and q, n ~> q + 2, there is a natural number E(n, q) satisfying the following:

(1) Let S be any set of points in the plane, no three on a line. If lSl ~> E(n, q), then there exists a convex n-gon whose points belong to S, for which the number of points of S in its interior is 0 (rood q).

(2) For fixed q, E(n,q) <~ 2 c~q)", c(q) is a constant depends on q only.

Part (1) was proved by Bialostocki et al.

[2] and our proof is aimed to simplify the original proof. The proof of Part ( 2) is completely new and reduces the huge upper bound of [2] (a super-exponential bound) to an exponential upper bound.

📜 SIMILAR VOLUMES

A new upper bound on the cyclic chromati
A new upper bound on the cyclic chromatic number
✍ O. V. Borodin; H. J. Broersma; A. Glebov; J. van den Heuvel 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 1 views

## Abstract A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^__c__^. Let Δ^\*^ be the maximum face degree of a graph. There exist

A New Upper Bound on the Cheeger Number
A New Upper Bound on the Cheeger Number of a Graph
✍ Sorin Dragomir; Elisabetta Barletta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Using a technique developed by A. Nilli (1991, Discrete Math. 91, 207 210), we estimate from above the Cheeger number of a finite connected graph G of small degree (2(G) 5) admitting sufficiently distant edges. ## 2001 Academic Press Let G=(V(G), E(G)) be a finite connected graph. The Cheeger numb