𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Proof of a Conjecture of Frankl and Füredi

✍ Scribed by Gurumurthi V. Ramanan

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
375 KB
Volume
79
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

We give a simple linear algebraic proof of the following conjecture of Frankl and Fu redi [7,9,13].

(Frankl

We generalise a method of Palisse and our proof-technique can be viewed as a variant of the technique used by Tverberg to prove a result of Graham and Pollak [10,11,14]. Our proof-technique is easily described. First, we derive an identity satisfied by a hypergraph F using its intersection properties. From this identity, we obtain a set of homogeneous linear equations. We then show that this defines the zero subspace of R |F| . Finally, the desired bound on |F| is obtained from the bound on the number of linearly independent equations. This proof-technique can also be used to prove a more general theorem (Theorem 2). We conclude by indicating how this technique can be generalised to uniform hypergraphs by proving the uniform Ray Chaudhuri Wilson theorem.

1997 Academic Press

1. Introduction

Let X be the n-element set [1, 2, 3, ..., n] and F a family of subsets of X. We call F a hypergraph on X. By P(X), we mean the set of all subsets of X and X (h) denotes the set of h-element subsets of X. When F X (h) we call F a h-uniform hypergraph.

📜 SIMILAR VOLUMES

Multilinear Polynomials and a Conjecture
Multilinear Polynomials and a Conjecture of Frankl and Füredi
✍ Arvind Sankar; Sundar Vishwanathan 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 86 KB

Frankl and Fu redi conjectured that given a family F of subsets of [n] such that 1 |E & F| k for all distinct E and F in F, we must have |F| k i=0 ( n&1 i

Proof of a Chromatic Polynomial Conjectu
Proof of a Chromatic Polynomial Conjecture
✍ F.M. Dong 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 138 KB

Let P(G, \*) denote the chromatic polynomial of a graph G. It is proved in this paper that for every connected graph G of order n and real number \* n, (\*&2) n&1 P(G, \*)&\*(\*&1) n&2 P(G, \*&1) 0. By this result, the following conjecture proposed by Bartels and Welsh is proved: P(G, n)(P(G, n&1))

Proof of a conjecture of Alan Hartman
Proof of a conjecture of Alan Hartman
✍ Liu, Q. Z.; Yap, H. P. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB 👁 2 views

A tree T is said to be bad, if it is the vertex-disjoint union of two stars plus an edge joining the center of the first star to an end-vertex of the second star. A tree T is good, if it is not bad. In this article, we prove a conjecture of Alan Hartman that, for any spanning tree T of K 2m , where

On a conjecture of Aris: Proof and remar
On a conjecture of Aris: Proof and remarks
✍ Dan Luss; Neal R. Amundson 📂 Article 📅 1967 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 428 KB 👁 2 views