𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Covering Non-uniform Hypergraphs

✍ Scribed by Endre Boros; Yair Caro; Zoltán Füredi; Raphael Yuster

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
160 KB
Volume
82
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let {(H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of {(H) taken over all hypergraphs H with n vertices and with no two hyperedges of the same size. We show that g(n)<1.98 -n(1+o(1)).

A special case corresponds to an old problem of Erdo s asking for the maximum number of edges in an n-vertex graph with no two cycles of the same length. Denoting this maximum by n+ f (n), we can show that f (n) 1.98 -n(1+o(1)).

Generalizing the above, let g(n, C, k) denote the maximum of {(H) taken over all hypergraph H with n vertices and with at most Ci k edges with cardinality i for all i=1, 2, ..., n. We prove that g(n, C, k)<(Ck!+1) n (k+1)Â(k+2) .

📜 SIMILAR VOLUMES

Approximate Set Covering in Uniform Hype
Approximate Set Covering in Uniform Hypergraphs
✍ Michael Krivelevich 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 296 KB

The weighted set covering problem, restricted to the class of r-uniform hypergraphs, is considered. We propose a new approach, based on a recent result of Aharoni, Holzman, and Krivelevich about the ratio of integer and fractional covering numbers in k-colorable r-uniform hypergraphs. This approach,

Constructing regular self-complementary
Constructing regular self-complementary uniform hypergraphs
✍ Shonda Gosselin 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB 👁 1 views

In this article, we examine the possible orders of t-subset-regular selfcomplementary k-uniform hypergraphs, which form examples of large sets of two isomorphic t-designs. We reformulate Khosrovshahi and Tayfeh-Rezaie's necessary conditions on the order of these structures in terms of the binary rep

Judicious Partitions of 3-uniform Hyperg
Judicious Partitions of 3-uniform Hypergraphs
✍ B. Bollobás; A.D. Scott 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 113 KB

A conjecture of Bollobás and Thomason asserts that, for r ≥ 1, every r -uniform hypergraph with m edges can be partitioned into r classes such that every class meets at least rm/(2r -1) edges. Bollobás, Reed and Thomason [3] proved that there is a partition in which every edge meets at least (1 -1/e

On line graphs of linear 3-uniform hyper
On line graphs of linear 3-uniform hypergraphs
✍ Metelsky, Yury; Tyshkevich, Regina 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 2 views

It is known that the class of line graphs of linear 3-uniform hypergraphs cannot be characterized by a finite list of forbidden induced subgraphs (R. N.

Singular coverings and non-uniform notio
Singular coverings and non-uniform notions of closed set computability
✍ Stéphane Le Roux; Martin Ziegler 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 250 KB

## Abstract The empty set of course contains no computable point. On the other hand, surprising results due to Zaslavskiĭ, Tseĭtin, Kreisel, and Lacombe have asserted the existence of non‐empty co‐r. e. closed sets devoid of computable points: sets which are even “large” in the sense of positive Le