John Talbot - Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{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 $\mathcal{K}_4^-$Article

Authors: John Talbot 1

  • 1 Department of Mathematics

We consider a new type of extremal hypergraph problem: given an $r$-graph $\mathcal{F}$ and an integer $k≥2$ determine the maximum number of edges in an $\mathcal{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].


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Extremal combinatorics,Turán-type problems,Hypergraphs,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 200 times.
This article's PDF has been downloaded 354 times.