# Many cliques with few edges

###### Abstract.

Recently Cutler and Radcliffe proved that the graph on vertices with maximum degree at most having the most cliques is a disjoint union of cliques of size together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with edges and maximum degree at most , the graph that has the most cliques of size at least two is the disjoint union of cliques of size together with the colex graph using the remainder of the edges. We have conjectured that in fact this graph has the largest number of ’s for all under the same conditions.

## 1. Introduction

There has been a lot of recent work on the general problem of determining which graphs have the most cliques subject to natural “resource limitations” and additional constraints. Most of the early work focused on vertices as resources, and added other conditions. There are results about -vertex graphs of maximum degree at most [2, 9], -vertex graphs containing no [14], and many related results concerning the number of independent sets in graphs [5, 8].

In this paper we consider results for which the resource is edges. We fix the number of edges in the graph, possibly impose other conditions, and ask which graph has the largest number of cliques.

Since we are putting no constraint on the number of vertices, the simplest version of the problem is that of determining

where we write for the number of cliques in of size and

for the number of cliques in of size at least . This question is straightforward to answer. The Kruskal-Katona Theorem [12, 10] easily shows that this maximum is achieved when ; the colex graph having edges. This is the graph on vertex set whose edges are the first in the colexicographic (colex) order on pairs.

Radcliffe and Uzzell noted that it is a straightforward consequence of the “rainbow Kruskal-Katona Theorem” of Frankl, Füredi, and Kalai [6], together with an important result of Frohmader [7] that

is achieved by the -partite colex-Turán graph . For more details see [13].

### 1.1. Main Result

In this paper we consider the next most natural problem in this area. We determine

Indeed we show that the maximum is attained by a graph made up of as many copies of as it is possible to build with edges, together with an additional component (possibly empty) that is a colex graph on strictly fewer than edges. For convenience we give a name to value of of this graph. Defining and by , we let

It is possible to describe the last term more carefully. For any there exist unique and defined by , . Moreover consists of a clique of size , together with another vertex joined to vertices of the clique. We have

Thus our main theorem is as follows.

###### Main Theorem.

For all , write with . If is a graph on edges with , then

(1) |

with equality if and only if .

In [11], we conjectured the following refinement of this main theorem.

###### Conjecture 2.

For any , if is a graph with edges and maximum degree at most , then

where and .

We proved this conjecture when and .

###### Theorem 3 ([11]).

For any , if is a graph with edges and maximum degree at most , then

where and .

Our proof of the main theorem combines several “local moves” (alterations to a potentially optimal graph demonstrating that a closely related graph would have a strictly larger value of ) and a final global averaging argument, applicable to any graph not containing a to which none of the local moves apply.

Our initial analysis of the structure of a potentially optimal graph is to consider *tight cliques*. A clique, of size say, is *tight* if its vertices have common neighbors. A maximal tight clique we call a *cluster*. We expect that optimal graphs will have many tight cliques. A cluster of size is simply a component in , and if such a cluster exists we can apply induction on . Most of our proof involves considering the possible structures and relationships of clusters.

In Section 2 we outline the basic properties of clusters. In Section 3 we discuss the various local alterations we will attempt to do on a potentially optimal graph.
All are variants of an operation we call *folding*, which was introduced in a slightly different context in [2] and also used in [3] and [11].
If we can establish that the folded graph has no more edges and no higher maximum degree than before, and has strictly increased, then we can eliminate as a potentially optimal graph.
In Section 4 we describe the final ingredients of the proof, and in Section 5 we prove our Main Theorem. We finish in Section 6 by describing some open problems in the area.

## 2. Clusters

One way to think about counting the number of cliques in a graph containing edges, is to count how the -cliques are made up of -cliques, how the -cliques are made up of -cliques, and so on. Clearly each -clique contains -cliques, and equally easily each -clique is contained in -cliques, where is the set of common neighbors of . Thus, for with maximum degree at most to have many cliques it seems likely that many of its cliques must have as large a common neighborhood as possible. This prompts the following definitions.

###### Definition 4.

If is a graph of maximum degree at most and is a clique satisfying we say that is *tight*. If is a maximal tight clique we say it is a *cluster*.

For a cluster we can analyze the graph locally as consisting of , its neighbors, and connections to the rest of the graph. The following definition establishes our notation and conventions.

###### Definition 5.

Suppose that is a graph with and is a cluster. We let and let be the graph of edges such that and . We define

i.e., the graph on whose edges are those not in . We think of the missing edges as *red edges*, and the edge from the cluster to the rest of the graph as *blue edges*. When the risk of confusion is low we will simply refer to , , , and . Note that since has maximum degree at most we know that for all vertices we have .