𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Scrambling permutations and entropy of hypergraphs

✍ Scribed by Zoltán Füredi

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
385 KB
Volume
8
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

The following result is proved by using entropy of hypergraphs. If r , , . . . , r,, are permutations of the n element set P such that for every triple x , y , z E P, one can find a ri such that ~~( x ) is between r i ( y ) and r i ( z ) , then n < exp(d/2). We also study k-scrambling permutations. Several problems remained open.

📜 SIMILAR VOLUMES

On splittable colorings of graphs and hy
On splittable colorings of graphs and hypergraphs
✍ Zoltán Füredi; Radhika Ramamurthi 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

## Abstract The notion of a split coloring of a complete graph was introduced by Erdős and Gyárfás [7] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an

Chromatic numbers of hypergraphs and cov
Chromatic numbers of hypergraphs and coverings of graphs
✍ Zevi Miller; Heinrich Müller 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

Burr recently proved [3] that for positive integers m , , m 2 , . . , , m, and any graph G we have x(G) 5 &, if and only if G can be expressed as the edge disjoint union of subgraphs F, satisfying x(F,) 5 m,. This theorem is generalized to hypergraphs. By suitable interpretations the generalization

Neighborhood hypergraphs of bipartite gr
Neighborhood hypergraphs of bipartite graphs
✍ Endre Boros; Vladimir Gurvich; Igor Zverovich 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB

## Abstract Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the litera

The Cartesian product of hypergraphs
The Cartesian product of hypergraphs
✍ Lydia Ostermeier; Marc Hellmuth; Peter F. Stadler 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB

## Abstract We show that every simple, (weakly) connected, possibly directed and infinite, hypergraph has a unique prime factor decomposition with respect to the (weak) Cartesian product, even if it has infinitely many factors. This generalizes previous results for graphs and undirected hypergraphs