𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Judicious Partitions of 3-uniform Hypergraphs

✍ Scribed by B. Bollobás; A.D. Scott

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

No coin nor oath required. For personal study only.

✦ Synopsis

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)m/3 ≈ 0.21m edges. Our main aim is to improve this result for r = 3. We prove that every 3-uniform hypergraph with m edges can be partitioned into three classes, each of which meets at least (5m -1)/9 edges. We also prove that for r > 3 we may demand 0.27m edges.

📜 SIMILAR VOLUMES

Judicious Partitions of Hypergraphs
Judicious Partitions of Hypergraphs
✍ B. Bollobás; A.D. Scott 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 348 KB

We prove the asymptotically best possible result that, for every integer k 2, every 3-uniform graph with m edges has a vertex-partition into k sets such that each set contains at most (1+o(1)) mÂk 3 edges. We also consider related problems and conjecture a more general result. 1997 Academic Press

Judicious partitions of bounded-degree g
Judicious partitions of bounded-degree graphs
✍ B. Bollobás; A. D. Scott 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

## Abstract We prove results on partitioning graphs __G__ with bounded maximum degree. In particular, we provide optimal bounds for bipartitions __V__(__G__) = __V__~1~ ∪ __V__~2~ in which we minimize {__e__(__V__~1~), __e__(__V__~2~)}. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 131–143, 200

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.

Uniform Partitions of 3-space, their Rel
Uniform Partitions of 3-space, their Relatives and Embedding
✍ Michel Deza; Mikhail Shtogrin 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 102 KB

We review 28 uniform partitions of 3-space in order to find out which of them have graphs (skeletons) embeddable isometrically (or with scale 2) into some cubic lattice Z n . We also consider some relatives of those 28 partitions, including Archimedean 4-polytopes of Conway-Guy, non-compact uniform

On a question of Sós about 3-uniform fri
On a question of Sós about 3-uniform friendship hypergraphs
✍ Stephen G. Hartke; Jennifer Vandenbussche 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB

## Abstract The well‐known Friendship Theorem states that if __G__ is a graph in which every pair of vertices has exactly one common neighbor, then __G__ has a single vertex joined to all others (a “universal friend”). V. Sós defined an analogous friendship property for 3‐uniform hypergraphs, and g