pith. machine review for the scientific record. sign in

arxiv: 1701.06139 · v1 · submitted 2017-01-22 · 🧮 math.CO

Recognition: unknown

Dense 3-uniform hypergraphs containing a large clique

Authors on Pith no claims yet
classification 🧮 math.CO
keywords denseuniformgraphhypergraphscontainingedgeshypergraphlambda
0
0 comments X
read the original abstract

An $r$-uniform graph $G$ is dense if and only if every proper subgraph $G'$ of $G$ satisfies $\lambda (G') < \lambda (G)$, where $\lambda (G)$ is the Lagrangian of a hypergraph $G$. In 1980's, Sidorenko showed that $\pi(F)$, the Tur\'an density of an $r$-uniform hypergraph $F$ is $r!$ multiplying the supremum of the Lagrangians of all dense $F$-hom-free $r$-uniform hypergraphs. This connection has been applied in estimating Tur\'an density of hypergraphs. When $r=2$, the result of Motzkin and Straus shows that a graph is dense if and only if it is a complete graph. However, when $r\ge 3$, it becomes much harder to estimate the Lagrangians of $r$-uniform hypergraphs and to characterize the structure of all dense $r$-uniform graphs. The main goal of this note is to give some sufficient conditions for $3$-uniform graphs with given substructures to be dense. For example, if $G$ is a $3$-graph with vertex set $[t]$ and $m$ edges containing $[t-1]^{(3)}$, then $G$ is dense if and only if $m \ge {t-1 \choose 3}+{t-2 \choose 2}+1$. We also give sufficient condition condition on the number of edges for a $3$-uniform hypergraph containing a large clique minus $1$ or $2$ edges to be dense.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.