𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the minimum size of tight hypergraphs

✍ Scribed by Jorge L. Arocha; Javier Bracho; Victor Neumann-Lara

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
333 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A k‐graph, H = (V, E), is tight if for every surjective mapping f: V → {1,….k} there exists an edge α ϵ E sicj tjat f|~α~ is injective. Clearly, 2‐graphs are tight if and only if they are connected. Bounds for the minimum number ϕ of edges in a tight k‐graph with n vertices are given. We conjecture that ϕ for every n and prove the equality when 2__n__ + 1 is prime. From the examples, minimal embeddings of complete graphs into surfaces follow. © 1992 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

On the Degree, Size, and Chromatic Index
On the Degree, Size, and Chromatic Index of a Uniform Hypergraph
✍ Noga Alon; Jeong Han Kim 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 274 KB

Let H be a k-uniform hypergraph in which no two edges share more than t common vertices, and let D denote the maximum degree of a vertex of H. We conjecture that for every =>0, if D is sufficiently large as a function of t, k, and =, then the chromatic index of H is at most (t&1+1Ât+=) D. We prove t

The size of minimum 3-trees
The size of minimum 3-trees
✍ Jorge L. Arocha; Joaquín Tey 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract A 3‐uniform hypergraph (3‐graph) is said to be tight, if for any 3‐partition of its vertex set there is a transversal triple. We give the final steps in the proof of the conjecture that the minimum number of triples in a tight 3‐graph on __n__ vertices is exactly $\left\lceil n(n-2)/3 \

New upper bounds on the minimum size of
New upper bounds on the minimum size of covering designs
✍ Iliya Bluskov; Heikki Hämäläinen 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

Let D = {B1 , B2 , . . . , B b } be a finite family of k-subsets (called blocks) of a vset X(v) = {1, 2, . . . , v} (with elements called points). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size

General Upper Bounds on the Minimum Size
General Upper Bounds on the Minimum Size of Covering Designs
✍ Iliya Bluskov; Katherine Heinrich 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 105 KB

Let D be a finite family of k-subsets (called blocks) of a v-set X(v). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks is the size of the covering, and the minimum size of the covering is called the covering nu

The Maximum Size of 3-Uniform Hypergraph
The Maximum Size of 3-Uniform Hypergraphs Not Containing a Fano Plane
✍ Dominique De Caen; Zoltán Füredi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 73 KB

A conjecture of V. So s [3] is proved that any set of 3 4 ( n 3 )+cn 2 triples from an n-set, where c is a suitable absolute constant, must contain a copy of the Fano configuration (the projective plane of order two). This is an asymptotically sharp estimate.