pith. sign in

arxiv: 1505.03210 · v1 · pith:Z2RNZEXNnew · submitted 2015-05-13 · 🧮 math.CO

Tur\'an numbers of hypergraph trees

classification 🧮 math.CO
keywords cross-cutgraphalphaestablishgraphshypergraphlargestnumber
0
0 comments X
read the original abstract

An $r$-graph is an $r$-uniform hypergraph tree (or $r$-tree) if its edges can be ordered as $E_1,\ldots, E_m$ such that $\forall i>1 \, \exists \alpha(i)<i$ such that $E_i\cap (\bigcup_{j=1}^{i-1} E_j)\subseteq E_{\alpha(i)}$. The Tur\'an number $ex(n,{\cal H})$ of an $r$-graph ${\cal H}$ is the largest size of an $n$-vertex $r$-graph that does not contain ${\cal H}$. A cross-cut of ${\cal H}$ is a set of vertices in ${\cal H}$ that contains exactly one vertex of each edge of ${\cal H}$. The cross-cut number $\sigma({\cal H})$ of ${\cal H}$ is the minimum size of a cross-cut of ${\cal H}$. We show that for a large family of $r$-graphs (largest within a certain scope) that are embeddable in $r$-trees, $ex(n,{\cal H})=(\sigma-1)\binom{n}{r-1}+o(n^{r-1})$ holds, and we establish structural stability of near extremal graphs. From stability, we establish exact results for some subfamilies.

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.