✦ LIBER ✦

Entropy Splitting Hypergraphs

✍ Scribed by Gábor Simonyi

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 367 KB
Volume: 66
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0024

No coin nor oath required. For personal study only.

✦ Synopsis

Hypergraph entropy is an information theoretic functional on a hypergraph with a probability distribution on its vertex set. It is sub-additive with respect to the union of hypergraphs. In case of simple graphs, exact additivity for the entropy of a graph and its complement with respect to every probability distribution on the vertex set gives a characterization of perfect graphs. Here we investigate uniform hypergraphs with an analoguous behaviour of their entropy. The main result is the characterization of 3-uniform hypergraphs having this entropy splitting property. It is also shown that for k 4 no non-trivial k-uniform hypergraph has this property.

📜 SIMILAR VOLUMES

Scrambling permutations and entropy of h

Scrambling permutations and entropy of hypergraphs

✍ Zoltán Füredi 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 385 KB

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.

Entropy Splitting for High-Order Numeric

Entropy Splitting for High-Order Numerical Simulation of Compressible Turbulence

✍ N.D. Sandham; Q. Li; H.C. Yee 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 156 KB

A stable high-order numerical scheme for direct numerical simulation (DNS) of shock-free compressible turbulence is presented. The method is applicable to general geometries. It contains no upwinding, artificial dissipation, or filtering. Instead the method relies on the stabilizing mechanisms of an

C-perfect hypergraphs

✍ Csilla Bujtás; Zsolt Tuza 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

## Abstract Let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{H}}=({{X}},{\mathcal{E}})$\end{document} be a hypergraph with vertex set __X__ and edge set \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{E}}$\end{document}. A C‐colori

Enumeration of Hypergraphs

✍ Toru Ishihara 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 87 KB

In this paper, we will study enumeration of hypergraphs. Let S p be a symmetric group acting on a p-setX . It induces the permutation group S \* p acting on the set of all subsets of X . Our problem is reduced to finding a good formula for the cycle index of S \* p . A crucial point is to calculate

Acyclic Hypergraph Projections

✍ Aviv Lustig; Oded Shmueli 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 157 KB

Hypergraphs can be partitioned into two classes: tree acyclic hypergraphs and cyclic hypergraphs. This paper analyzes a new class of cyclic hypergraphs called Xrings. Hypergraph H is an Xring if the hyperedges of H can be circularly ordered so that for every vertex, all hyperedges containing the ver

Hamiltonian chains in hypergraphs

✍ Katona, Gyula Y.; Kierstead, H. A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

A cyclic ordering of the vertices of a k-uniform hypergraph is called a hamiltonian chain if any k consecutive vertices in the ordering form an edge. For k = 2 this is the same as a hamiltonian cycle. We consider several natural questions about the new notion. The main result is a Dirac-type theorem