𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On conjectures of Frankl and El-Zahar

✍ Scribed by Bernardo Llano; Juan José Montellano-Ballesteros; Eduardo Rivera-Campo; Ricardo Strausz

Book ID
102345587
Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
135 KB
Volume
57
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An induced subgraph ${\cal S}$ of a graph ${\cal G}$ is called a derived subgraph of ${\cal G}$ if ${\cal S}$ contains no isolated vertices. An edge e of ${\cal S}$ is said to be residual if e occurs in more than half of the derived subgraphs of ${\cal S}$. In this article, we prove that every simple graph with at least one edge contains a non‐residual edge. This was conjectured by El‐Zahar in 1997. © 2008 Wiley Periodicals, Inc. J Graph Theory 57: 344–352, 2008

📜 SIMILAR VOLUMES

Proof of a Conjecture of Frankl and Füre
Proof of a Conjecture of Frankl and Füredi
✍ Gurumurthi V. Ramanan 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 375 KB

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

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

Standard monomials forq-uniform families
Standard monomials forq-uniform families and a conjecture of Babai and Frankl
✍ Gábor Hegedűs; Lajos Rónyai 📂 Article 📅 2003 🏛 SP Versita 🌐 English ⚖ 224 KB

Let n; k; ¬ be integers, n; ¬ > 0, p be a prime and q = p . Consider the complete q-uniform family F (k; q) = fK [n] : jKj ² k (mod q)g: We study certain inclusion matrices attached to F (k; q) over the eld F p . We show that if `µ q ¡ 1 and 2`µ n then rank p I(F (k; q); This extends a theorem of