Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-16T17:01:17.968Z Has data issue: false hasContentIssue false

Edge Distribution of Graphs with Few Copies of a Given Graph

Published online by Cambridge University Press:  14 August 2006

V. NIKIFOROV
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA (e-mail: [email protected])

Abstract

We show that if a graph contains few copies of a given graph, then its edges are distributed rather unevenly.

In particular, for all $\varepsilon > 0$ and $r\geq2$, there exist $\xi =\xi (\varepsilon,r) > 0$ and $k=k (\varepsilon,r)$ such that, if $n$ is sufficiently large and $G=G(n)$ is a graph with fewer than $\xi n^{r}$$r$-cliques, then there exists a partition $V(G) =\cup_{i=0}^{k}V_{i}$ such that \[ \vert V_{i}\vert =\lfloor n/k\rfloor \quad \text{and} \quad e(W_{i}) <\varepsilon\vert V_{i}\vert ^{2}\] for every $i\in [k]$.

We deduce the following slightly stronger form of a conjecture of Erdős.

For all $c>0$ and $r\geq3$, there exist $\xi=\xi (c,r) >0$ and $\beta=\beta(c,r)>0$ such that, if $n$ is sufficiently large and $G=G(n,\lceil cn^{2} \rceil)$ is a graph with fewer than $\xi n^{r}$$r$-cliques, then there exists a partition $V(G) =V_{1}\cup V_{2}$ with $ \vert V_{1} \vert = \lfloor n/2 \rfloor $ and $\vert V_{2} \vert = \lceil n/2 \rceil $ such that \[ e(V_{1},V_{2}) > (1/2+\beta) e (G).\]

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)