Article ID Journal Published Year Pages File Type
4654846 European Journal of Combinatorics 2007 18 Pages PDF
Abstract

We consider a new type of extremal hypergraph problem: given an rr-graph FF and an integer k≥2k≥2 determine the maximum number of edges in an FF-free, kk-colourable rr-graph on nn vertices.Our motivation for studying such problems is that it allows us to give a new upper bound for an old Turán problem. We show that a 3-graph in which any four points span at most two edges has density less than 0.32975<13−1280, improving previous bounds of 13 due to de Caen [D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs, Ars Combin. 16 (1983) 5–10], and 13−4.5305×10−6 due to Mubayi [D. Mubayi, On hypergraphs with every four points spanning at most two triples, Electron. J. Combin. 10 (10) (2003)].

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,