pith. sign in

arxiv: 2002.07350 · v1 · pith:IWVCAKJGnew · submitted 2020-02-18 · 🧮 math.CO

Induced Tur\'an problems and traces of hypergraphs

classification 🧮 math.CO
keywords inducedbergecontainsdenoteedgesgraphhypergraphmaximum
0
0 comments X
read the original abstract

Let $F$ be a graph. We say that a hypergraph $H$ contains an induced Berge $F$ if the vertices of $F$ can be embedded to $H$ (e.g., $V(F)\subseteq V(H)$) and there exists an injective mapping $f$ from the edges of $F$ to the hyperedges of $H$ such that $f(xy) \cap V(F) = \{x,y\}$ holds for each edge $xy$ of $F$. In other words, $H$ contains $F$ as a trace. Let $ex_{r}(n,B_{ind} F)$ denote the maximum number of edges in an $r$-uniform hypergraph with no induced Berge $F$. Let $ex(n,K_r, F)$ denote the maximum number of $K_r$'s in an $F$-free graph on $n$ vertices. We show that these two Tur\'an type functions are strongly related.

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.