The Density Tur\'an problem
read the original abstract
Let $H$ be a graph on $n$ vertices and let the blow-up graph $G[H]$ be defined as follows. We replace each vertex $v_i$ of $H$ by a cluster $A_i$ and connect some pairs of vertices of $A_i$ and $A_j$ if $(v_i,v_j)$ was an edge of the graph $H$. As usual, we define the edge density between $A_i$ and $A_j$ as $d(A_i,A_j)=\frac{e(A_i,A_j)}{|A_i||A_j|}.$ We study the following problem. Given densities $\gamma_{ij}$ for each edge $(i,j)\in E(H)$. Then one has to decide whether there exists a blow-up graph $G[H]$ with edge densities at least $\gamma_{ij}$ such that one cannot choose a vertex from each cluster so that the obtained graph is isomorphic to $H$, i.e, no $H$ appears as a transversal in $G[H]$. We call $d_{crit}(H)$ the maximal value for which there exists a blow-up graph $G[H]$ with edge densities $d(A_i,A_j)=d_{crit}(H)$ $((v_i,v_j)\in E(H))$ not containing $H$ in the above sense. Our main goal is to determine the critical edge density and to characterize the extremal graphs.
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.