Back to Search
Start Over
The Density Tur\'an problem
- Source :
- Combinatorics, Probability and Computing, 21 (4), (2012), 531-553
- Publication Year :
- 2014
-
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.
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- Combinatorics, Probability and Computing, 21 (4), (2012), 531-553
- Publication Type :
- Report
- Accession number :
- edsarx.1407.7873
- Document Type :
- Working Paper