Unavoidable stars in 3-graphs

DOI10.1016/0097-3165(83)90011-0MaRDI QIDQ793053zbMATH OpenOpenAlexFDO

Authors Fan Chung

Publication date 1983

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(83)90011-0

zbMATH Keywords

Delta-systemsextremal hypergraph problems

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal problems in graph theory (05C35) Hypergraphs (05C65)

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.

Recommendations

• The maximum number of edges in a 3-graph not containing a given star
• A structural result for 3-graphs
• On unavoidable hypergraphs
• Erdős--Ko--Rado for three sets
• The maximum size of 3-wise intersecting and 3-wise union families

Cited in

(11)

• The maximum number of edges in a 3-graph not containing a given star
• Unavoidable hypergraphs
• Light 3-stars in embedded graphs
• Soft 3-stars in sparse plane graphs
• Turán numbers of sunflowers
• A structural result for 3-graphs
• Uniform Star-factors of Graphs with Girth Three
• Universal and unavoidable graphs
• The maximum number of triangles in \(F_k\)-free graphs
• Linear dependencies, polynomial factors in the Duke-Erdős forbidden sunflower problem
• Extremal subgraphs for two graphs

This page was built for publication: Unavoidable stars in 3-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q793053)