pipette
ESEspañol

Tur\'an densities of hypergraph augmentations

Oleg Pikhurko, Jiabao Yang, Xiutao Zhu

Preprint

In the authors' words

For a -graph and an integer , the -augmentation is the -graph obtained by adding the same set of new vertices to every edge of . We investigate the behaviour of the Tur\'an density , which is the asymptotically maximum edge density of a large -free -graph, as a function of . Let be the -augmentation of the complete -graph on vertices; equivalently, is the (unique up to isomorphism) -graph with vertices and edges. This paper determines the Tur\'an density of each -graph within a constant factor and estimates the lower bounds on coming from the circular construction of Sidorenko. In particular, it is shown that if then . Also, we consider augmentations of graphs (that is, the case ) and prove that for every 3-chromatic graph , which comes close to the known upper bound . Note that, for all other graphs , the function is known to be either identically 0 or uniformly bounded away from 0.

Main resultLimitation the authors admit

Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.