Unavoidable stars in 3-graphs
type: Item
instance of: scholarly article
title: Unavoidable stars in 3-graphs
zbMATH Open document ID: 0538.05049
DOI: 10.1016/0097-3165(83)90011-0
published in: Journal of Combinatorial Theory. Series A
publication date: 1983-01-01T00:00:00Z
review text: Denote by f(n,k) the maximal size of a family of 3-subsets of an n-set, not containing k members with the same one-element pairwise intersection (a k-star). Improving earlier bounds by \textit{R. A. Duke} and \textit{P. Erdős} [Proc. 8th Southeast Conf. on Combinatorics, Graph Theory and Computing, Baton Rouge 1977, 247-252 (1977; Zbl 0443.05002)] and \textit{P. Frankl} [Acta Math. Acad. Sci. Hung. 32, 157-160 (1978; Zbl 0407.05013)], the author proves \(k(k-1)(n-(5k+2)/3)\leq f(n,k)\leq k(k-1)n\) for k odd, \(k(k-3/2)(n-k-2)+2k-3\leq f(n,k)\leq(k-1)(k-1/2)n\) for k even. The proof uses a tricky weight-function on the pairs of the underlying set.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 3855158
zbMATH Keywords: extremal hypergraph problems
zbMATH Keywords: Delta-systems
author: Fan Chung
reviewed by: Péter Komjáth
MaRDI profile type: Publication
full work available at URL: 0097-3165(83)90011-0
OpenAlex ID: W2061954628
description: scientific article; zbMATH DE number 3855158