Graphs with many r-cliques have large complete r-partite subgraphs

We study the maximum number of $r$-vertex cliques in $(r-1)$-uniform hypergraphs not containing complete $r$-partite hypergraphs $K_r^{(r-1)}(a_1, \dots, a_r)$. By using the hypergraph removal lemma, we show that this maximum is $o( n^{r - 1/(a_1 \cdots a_{r-1})} )$. This immediately implies the corresponding results of Mubayi and Mukherjee and of Balogh, Jiang, and Luo for graphs. We also provide a lower bound by using hypergraph Tur\'an numbers.

Let $r \ge 3$ be fixed and $G$ be an $n$-vertex graph. A long-standing conjecture of Gy{\H o}ri states that if $e(G) = t_{r-1}(n) + k$, where $t_{r-1}(n)$ denotes the number of edges of the Tur{\'a}n graph on $n$ vertices and $r - 1$ parts, then $G$ has at least $(2 - o(1))k/r$ edge disjoint $r$-cliques. We prove this conjecture.

Affirming a conjecture of Erd\H{o}s and Renyi we prove that for any (real number) c_1>0 for some c_2>0, if a graph G has no c_1(log n) nodes on which the graph is complete or edgeless (i.e. G exemplifies |G| not-> (c_1 log n)^2_2) then G has at least 2^{c_2n} non-isomorphic (induced) subgraphs.

We prove that for each integer $r\geq 2$, there exists a constant $C_r>0$ with the following property: for any $0<\varepsilon \leq 1/2$ and any graph $G$ with clique number at most $r,$ there is a partition of $V(G)$ into at most $(1/\varepsilon)^{C_r}$ sets $S_1, \dots, S_t,$ such that $G[S_i]$ has maximum degree at most $\varepsilon |S_i|$ for each $1 \leq i \leq t.$ This answers a question of Fox, Nguyen, Scott and Seymour, who proved a similar result for graphs with no in...

Let $Q(n,c)$ denote the minimum clique number over graphs with $n$ vertices and chromatic number $c$. We determine the rate of growth of of the sequence ${Q(n,\lceil rn \rceil)}_{n=1}^\infty$ for any fixed $0<r\leq 1$. We also give a better upper bound for $Q(n,\lceil rn \rceil)$.

A graph on $n$ vertices is said to be \emph{$C$-Ramsey} if every clique or independent set of the graph has size at most $C \log n$. The only known constructions of Ramsey graphs are probabilistic in nature, and it is generally believed that such graphs possess many of the same properties as dense random graphs. Here, we demonstrate one such property: for any fixed $C>0$, every $C$-Ramsey graph on $n$ vertices induces subgraphs of at least $n^{2-o(1)}$ distinct sizes. This ne...

For two graphs $F,H$ and a positive integer $n$, the function $f_{F,H}(n)$ denotes the largest $m$ such that every $H$-free graph on $n$ vertices contains an $F$-free induced subgraph on $m$ vertices. This function has been extensively studied in the last 60 years when $F$ and $H$ are cliques and became known as the Erd\H{o}s-Rogers function. Recently, Balogh, Chen and Luo, and Mubayi and Verstra\"ete initiated the systematic study of this function in the case where $F$ is a ...

In 1977, Erd\H{o}s and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $ |G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has been no improvement on this result (for general $H$). We prove a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique ...

We prove that if $G$ is a $k$-partite graph on $n$ vertices in which all of the parts have order at most $n/r$ and every vertex is adjacent to at least a $1-1/r+o(1)$ proportion of the vertices in every other part, then $G$ contains the $(r-1)$-st power of a Hamiltonian cycle

Suppose $0 < p \le \infty$. For a simple graph $G$ with a vertex-degree sequence $d_1, \dots, d_n$ satisfying $(d_1^p + \dots + d_n^p)^{1/p} \le C$, we prove asymptotically sharp upper bounds on the number of $t$-cliques in $G$. This result bridges the $p = 1$ case, which is the notable Kruskal--Katona theorem, and the $p = \infty$ case, known as the Gan--Loh--Sudakov conjecture, and resolved by Chase. In particular, we demonstrate that the extremal construction exhibits a di...