Search

This paper deals with extremal problems concerning colorings of partial Steiner systems. We establish a new sufficient condition for r-colorability of a hypergraph from some class of such systems in terms of maximum vertex degree. Moreover, as a corollary we obtain a new lower bound for the threshold probability for r-colorability of a random hypergraph in a binomial model. [ABSTRACT FROM AUTHOR]

Abstract: In this short survey, some approaches that can be used to solve the generalized -design problem are considered. Special cases of the generalized -design problem include well-known conjectures for -designs, degree sequences of graphs and hypergraphs, and partial Steiner systems. Also described are some related problems such as the characterization of -vectors of pure simplicial complexes, which are well known but little understood. Some suggestions how enumerative and polyhedral techniques may help are also described. [Copyright &y& Elsevier]

Abstract: A friendship 3-hypergraph is a 3-hypergraph in which for any 3 distinct vertices , and , there exists a unique fourth vertex such that , , are 3-hyperedges. Sós constructed friendship 3-hypergraphs using Steiner triple systems. Hartke and Vandenbussche showed that any friendship 3-hypergraph can be partitioned into ’s. (A is the set of four hyperedges of size three that can be formed from a set of 4 elements.) These ’s form a set of 4-tuples which we call a friendship design. We define a geometric friendship design to be a resolvable friendship design that can be embedded into an affine geometry. Refining the problem from friendship designs to geometric friendship designs allows us to state some structure results about these geometric friendship designs and decrease the search space when searching for geometric friendship designs. Hartke and Vandenbussche discovered 5 new examples of friendship designs which happen to be geometric friendship designs. We show the 3 non-isomorphic geometric designs on 16 vertices are the only such non-isomorphic geometric designs on 16 vertices. We also improve the known lower and upper bounds on the number of hyperedges in any friendship 3-hypergraph. Finally, we show that no friendship 3-hypergraph exists on 11 or 12 points. [Copyright &y& Elsevier]