You are currently browsing the monthly archive for April 2007.

The question in extremal graph theory I wish to discuss here originates from Luca Trevisan; it shows that we still don’t know everything that we should about the “local” properties of large dense graphs.

Let $G = (V,E)$ be a large (undirected) graph, thus V is the vertex set with some large number n of vertices, and E is the collection of edges {x,y} connecting two vertices in the graph. We can allow the graph to have loops {x,x} if one wishes; it’s not terribly important for this question (since the number of loops is so small compared to the total number of edges), so let’s say there are no loops. We define three quantities of the graph G:

• The edge density $0 \leq \alpha \leq 1$, defined as the number of edges in G, divided by the total number of possible edges, i.e. $n(n-1)/2$;
• The triangle density $0 \leq \beta \leq 1$, defined as the number of triangles in G (i.e. unordered triplets {x,y,z} such that {x,y},{y,z}, {z,x} all lie in G), divided by the total number of possible triangles, namely $n(n-1)(n-2)/6$;
• The diamond density $0 \leq \gamma \leq 1$, defined as the number of diamonds in G (i.e. unordered pairs { {x,y,z}, {x,y,w} } of triangles in G which share a common edge), divided by the total number of possible diamonds, namely $n(n-1)(n-2)(n-3)/4$.