Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 453.05050
Autor: Duke, Richard A.; Erdös, Paul
Title: A problem on complements and disjoint edges in hypergraph. (In English)
Source: Combinatorics, graph theory and computing, Proc. 11th southeast. Conf., Boca Raton/Florida 1980, Vol. I, Congr. Numerantium 28, 369-375 (1980).
Review: [For the entire collection see Zbl 444.00009.]
The authors denote by r(s,N,t; k), N > k, the least integer m such that every 2-coloring of the edges of a complete k-graph on m vertices produces either a matching with s edges in the first color or a complete k-graph on N vertice with at most t edges in the first color. In the first part of the paper, the authors consider several questions dealing with the ffunction r(s,N,t; k) arriving, finally, at the following conjecture.Given k and n, n \geq 2k, if H is a k-graph on n vertices which is such that each subset of k-1 vertices of H missses at least k edges of H, then H must possess at least two disjoint edges. After establishing the conjecture is not correct in general, the authors formulate a few questions strictly related to conjecture (for example, wath is the smallest value of k for which there is a counterexample to the conjecture).
Reviewer: L.Zaremba
Classif.: * 05C65 Hypergraphs
05C70 Factorization, etc.
05C55 Generalized Ramsey theory
Keywords: matching; Ramsey number; k-graph; hypergraph
Citations: Zbl.444.00009
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag