Irrepresentability by multiple intersection, or why the interval number is unbounded (Q1065021)

The known interval number of graphs is extended to the \(\Sigma\)-number and P-number of graphs. The \(\Sigma\)-number of a graph G is the least possible integer t such that G is the intersection graph of sets consisting of at most t sets from a given family of sets \(\Sigma\). Let P be a class of graphs. Then the P-number of a graph G is the least possible integer t such that G can arise from a graph \(H\in P\) by the contraction of suitable disjoined vertex sets with cardinalities \(\leq t\). For the \(\Sigma\)-number is proved: If \(\Sigma\) is the family of a) all curves on a 2-dimensional manifold with finite Euler characteristic, b) all d-dimensional boxes \(R^ d\), c) all planar convex sets, d) all line segments in \(R^ d\), then the \(\Sigma\)-number is unbounded. The main result concerning the P-number of graphs gives the theorem: Let P be a monotone class of graphs (i.e. a class containing with every graph also each of its induced subgraphs). Then the following statements are equivalent: (1) The P-number is bounded; (2) All graphs have the P-number \(\leq 2\); (3) The class P contains all bipartite graphs. This theorem is also generalized for k-uniform hypergraphs and simplicial complexes (i.e. hypergraphs containing with every edge e also all edges e' for which \(\emptyset \neq V(e')\subset V(e))\). E.g. for k-uniform hypergraphs it is the theorem: If P is a monotone family of k-uniform hypergraphs, then the next statements are equivalent: (1) The P-number of hypergraphs is bounded; (2) All k-uniform hypergraphs have the P-number \(\leq k\); (3) The class P contains all k-partite k-uniform hypergraphs.