On partitioning of hypergraphs (Q879389): Difference between revisions

The edge-isoperimetric problem on graphs (EIP), namely for a given integer \(m\) and graph \(G=(V,E)\) to find a subset \(A\) of the vertices of \(G\) of cardinality \(m\) so that the number of edges of \(G\) connecting vertices in \(A\) to vertices in \(V\setminus A\), is minimized (version 1), or such that the number of edges of \(G\) induced by \(A\) is maximized (version 2), is generalized to hypergraphs. Following his methods developed in [\textit{S. L. Bezrukov}, J. Discrete Math. 203, No.~1--3, 9--22 (1999; Zbl 0932.05044)] the authors establish a representation of hypergraphs by posets and apply some results from Macaulay theory on posets to the EIP on hypergraphs. Four families of hypergraphs admitting nested solutions for the EIP (in both verions) are presented.