𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes

✍ Scribed by Tamás Fleiner; Volker Kaibel; Günter Rote

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
157 KB
Volume
21
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

We prove two new upper bounds on the number of facets that a d-dimensional 0/1-polytope can have. The first one is 2(d -1)!+2(d -1) (which is the best one currently known for small dimensions), while the second one of O((d -2)!) is the best known bound for large dimensions.

📜 SIMILAR VOLUMES

An improved upper bound on the crossing
An improved upper bound on the crossing number of the hypercube
✍ Luerbio Faria; Celina Miraglia Herrera de Figueiredo; Ondrej Sýkora; Imrich Vrt' 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB

## Abstract We draw the __n__‐dimensional hypercube in the plane with ${5\over 32}4^{n}-\lfloor{{{{n}^{2}+1}\over 2}}\rfloor {2}^{n-2}$ crossings, which improves the previous best estimation and coincides with the long conjectured upper bound of Erdös and Guy. © 2008 Wiley Periodicals, Inc. J Graph

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

On an upper bound for the harmonious chr
On an upper bound for the harmonious chromatic number of a graph
✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.

On some simple degree conditions that gu
On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
✍ Vu, Van H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 2 views

It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/ log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-menti

An upper bound on the ramsey number R(K3
An upper bound on the ramsey number R(K3, G) depending only on the size of the graph G
✍ A. F. Sidorenko 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB 👁 1 views

## Abstract Harary stated the conjecture that for any graph __G__ with __n__ edges and without isolated vertices __r__(__K__~3~,__G__) ⩽ 2__n__ + 1. Erdös, Faudree, Rousseau, and Schelp proved that __r__(__K__~3~,__G__) ⩽ ⌈8/3__n__⌉. Here we prove that __r__(__K__~3~,__G__) ⩽ ⌊5/2__n__⌋ −1 for __n_