Hypergraph Turán Problems in ℓ2-Norm

Thumbnail Image
Date
2021-08-25
Authors
Balogh, József
Clemen, Felix Christian
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

There are various different notions measuring extremality of hypergraphs. In this survey we compare the recently introduced notion of the codegree squared extremal function with the Turán function, the minimum codegree threshold and the uniform Turán density.
The codegree squared sum co2(G) of a 3-uniform hypergraph G is defined to be the sum of codegrees squared d(x,y)2 over all pairs of vertices x,y. In other words, this is the square of the ℓ2-norm of the codegree vector. We are interested in how large co2(G) can be if we require G to be H-free for some 3-uniform hypergraph H. This maximum value of co2(G) over all H-free n-vertex 3-uniform hypergraphs G is called the codegree squared extremal function, which we denote by exco2(n,H). We systemically study the extremal codegree squared sum of various 3-uniform hypergraphs using various proof techniques. Some of our proofs rely on the flag algebra method while others use more classical tools such as the stability method. In particular, we (asymptotically) determine the codegree squared extremal numbers of matchings, stars, paths, cycles, and F5, the 5-vertex hypergraph with edge set {123,124,345}.
Additionally, our paper has a survey format, as we state several conjectures and give an overview of Turán densities, minimum codegree thresholds and codegree squared extremal numbers of popular hypergraphs.

Series Number
Journal Issue
Is Version Of
Book chapter
Hypergraph Turán Problems in ℓ2-Norm
(Cambridge University Press, 2022) Balogh, József ; Clemen, Felix Christian ; Lidicky, Bernard ; Mathematics
There are various different notions measuring extremality of hypergraphs. In this survey we compare the recently introduced notion of the codegree squared extremal function with the Turán function, the minimum codegree threshold and the uniform Turán density.
The codegree squared sum co₂(G) of a 3-uniform hypergraph G is defined to be the sum of codegrees squared d(x, y)² over all pairs of vertices x, y. In other words, this is the square of the ℓ2-norm of the codegree vector. We are interested in how large co₂(G) can be if we require G to be H-free for some 3-uniform hypergraph H. This maximum value of co₂(G) over all H- free n-vertex 3-uniform hypergraphs G is called the codegree squared extremal function, which we denote by exco₂(n, H).
We systemically study the extremal codegree squared sum of various 3- uniform hypergraphs using various proof techniques. Some of our proofs rely on the flag algebra method while others use more classical tools such as the stability method. In particular, we (asymptotically) determine the codegree squared extremal numbers of matchings, stars, paths, cycles, and F₅, the 5- vertex hypergraph with edge set {123,124,345}.
Additionally, our paper has a survey format, as we state several conjectures and give an overview of Turán densities, minimum codegree thresholds and codegree squared extremal numbers of popular hypergraphs.
Versions
Series
Academic or Administrative Unit
Type
article
Comments

This preprint is made available through arXiv: https://arxiv.org/abs/2108.10406.

Rights Statement
Copyright
Fri Jan 01 00:00:00 UTC 2021
Funding
DOI
Supplemental Resources
Source
Collections