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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page