3-uniform hypergraphs: modular decomposition and realization by tournaments





Let $H$ be a 3-uniform hypergraph. A tournament $T$ defined on $V(T)=V(H)$ is a realization of $H$ if the edges of $H$ are exactly the 3-element subsets of $V(T)$ that induce 3-cycles. We characterize the 3-uniform hypergraphs that admit realizations by using a suitable modular decomposition.


P. Bonizzoni, G. Della Vedova, An algorithm for the modular decomposition of hypergraphs, J. Algorithms 32 (1999) 65--86.

A. Boussa"{i}ri, P. Ille, G. Lopez, S. Thomass'e,

The $C_{3}$-structure of the tournaments,

Discrete Math. 277 (2004) 29--43.

M. Chein, M. Habib, M.C. Maurer,

Partitive hypergraphs, Discrete Math. 37 (1981) 35--50.

A. Ehrenfeucht, T. Harju, G. Rozenberg,

The Theory of 2-Structures, A Framework for Decomposition and

Transformation of Graphs, World Scientific, Singapore, 1999.

bibitem{ER90b}A. Ehrenfeucht, G. Rozenberg,

Theory of 2-structures, Part II: representations through tree labelled families,

Theoret. Comput. Sci. 70 (1990) 305--342.

N.D. Filippov, L.N. Shevrin,

Partially ordered sets and their comparability graphs,

Siberian Math. J. 11 (1970) 497--509.

P. Frankl, Z. F"{u}redi, An exact result for 3-graphs, Discrete Math. 50 (1984) 323--328.

T. Gallai,

Transitiv orientierbare Graphen,

Acta Math. Acad. Sci. Hungar. 18 (1967) 25--66.

A. Ghouila-Houri, Caract'erisation des graphes non orient'es dont

on peut orienter les ar^{e}tes de mani`{e}re `{a} obtenir le graphe d'une

relation d'ordre, C. R. Acad. Sci. Paris S'erie I 254 (1962) 1370--1371.

D. Haglin, M. Wolf, On convex subsets in tournaments,

SIAM J. Discrete Math. 9 (1996) 63--70.

P. Ille, J.-X. Rampon,

A Counting of the minimal realizations of the posets of dimension two, Ars Combin. 78 (2006) 157--165.

P. Ille, R. Woodrow,

Weakly partitive families on infinite sets, Contrib. Discrete Math. 4 (2009) 54--80.

D. Kelly, Comparability graphs, in: I. Rival (Ed.), Graphs and Orders, Reidel Publishing, 1985,


F. Maffray, M. Preissmann,

A translation of Tibor Gallai's paper: Transitiv orientierbare


in: J.L. Ramirez-Alfonsin and B.A. Reed (Eds.),

Perfect Graphs, Wiley,

New York, 2001, pp.~25--66.

J.H. Schmerl, W.T. Trotter, Critically indecomposable

partially ordered sets, graphs, tournaments and other binary relational structures,

Discrete Math. 113 (1993) 191--205.

J. Spinrad,

P4-trees and substitution decomposition,

Discrete Appl. Math. 39 (1992) 263--291.