John Talbot
-
Chromatic Turán problems and a new upper bound for the Turán density of K−4
dmtcs:3437 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3437
Chromatic Turán problems and a new upper bound for the Turán density of K−4Conference paper
Authors: John Talbot 1
NULL
John Talbot
1 Department of Mathematics
We consider a new type of extremal hypergraph problem: given an r-graph F and an integer k≥2 determine the maximum number of edges in an F-free, k-colourable r-graph on n vertices. Our motivation for studying such problems is that it allows us to give a new upper bound for an old problem due to Turán. We show that a 3-graph in which any four vertices span at most two edges has density less than \frac{33}{ 100}, improving previous bounds of \frac{1}{ 3} due to de Caen [1], and \frac{1}{ 3}-4.5305×10^-6 due to Mubayi [9].