Skip to Main content Skip to Navigation
Conference papers

Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{K}_4^-$

Abstract : 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].
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184394
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:39:29 AM
Last modification on : Thursday, May 11, 2017 - 1:02:51 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:06:40 AM

File

dmAE0116.pdf
Publisher files allowed on an open archive

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-01184394, version 1

Collections

Citation

John Talbot. Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{K}_4^-$. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.77-80. ⟨hal-01184394⟩

Share

Metrics

Record views

137

Files downloads

621