Mathematics – Combinatorics
Scientific paper
2009-03-02
Mathematics
Combinatorics
Scientific paper
The theorem of Chung, Graham, and Wilson on quasi-random graphs asserts that of all graphs with edge density p, the random graph G(n,p) contains the smallest density of copies of K_{t,t}, the complete bipartite graph of size 2t. Since K_{t,t} is a t-blowup of an edge, the following intriguing open question arises: Is it true that of all graphs with triangle density p^3, the random graph G(n,p) contains the smallest density of K_{t,t,t}, which is the t-blowup of a triangle? Our main result gives an indication that the answer to the above question is positive by showing that for some blowup, the answer must be positive. More formally we prove that if G has triangle density p^3, then there is some 2 <= t <= T(p) for which the density of K_{t,t,t} in G is at least p^{(3+o(1))t^2}, which (up to the o(1) term) equals the density of K_{t,t,t} in G(n,p). We also consider the analogous question on skewed blowups, showing that somewhat surprisingly, the behavior there is different. We also raise several conjectures related to these problems and discuss some applications to other areas.
Shapira Asaf
Yuster Raphael
No associations
LandOfFree
On the Density of a Graph and its Blowup does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Density of a Graph and its Blowup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Density of a Graph and its Blowup will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-77509