3
$\begingroup$

Let $G$ be a random graph with $n$ vertices, and let $\delta(G)$ be the maximum number of triangles in $G$.

Question. How to prove the bound $$P(\delta(G)) \leq m - t \sqrt{f(m)}) \leq 2e^{-t^2 / 4}$$ using Talagrand's concentration Inequality? Here $m$ denotes the median of $\delta(G)$.

I am trying to use the convex distance inequality to get this bound.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

There is a (lovely) corollary of Talagrand's inequality contained in Alon and Spencer's Probabilistic Method which gives it immediately. Here's a version of it:

Definition: Let $f: N \to N$ be a function. A function $h$ is $f$-certifiable if whenever $h(x) \geq s$ there exists $I \subset \{1,\ldots,n\}$ with $|I| \leq f(s)$ so that for all $y$ that agree with $x$ on the coordinates $I$ we have $h(y) \geq s$.

In particular the number of triangles in a graph is $3s$ certifiable, since if there are $\geq s$ triangles, we can produce $3s$ edges which "certify" the existence of $s$ triangles. Now we have a nice corollary of Talagrand's inequality:

Theorem (Talagrand): Let $X = h(\cdot)$ where $h$ is $f$ certifiable and $1$-Lipschitz. Then for all $b$ and $t$ we have $$P(X \leq b - t\sqrt{f(b)}) P(X \geq b) \leq e^{-t^2 / 4}\,.$$

The number of edge disjoint triangles in a random graph is certainly $1$-Lipschitz, and is $3s$ certifiable. Applying the above for $b = m$ completes the proof.

Improve this answer
$\endgroup$
2
  • $\begingroup$ can you explain how the edge disjoint triangles is 1-Lipschitz? $\endgroup$
    – user178238
    Commented Apr 22, 2021 at 12:47
  • $\begingroup$ Sure, what it means to be $1$-Lipschitz is that if you add or remove an edge, then the maximum number of edge disjoint triangles changes by at most by 1. There are many ways to see that this holds. In the case where you remove an edge, it's pretty clear that it can only drop by 1, since it must have been in at most 1 triangle in the max. If you add an edge, suppose it increases by $\geq 2$ triangles; then only at most one triangle can include this edge, meaning we'd have made a collection for our original graph with 1 more triangle than the max. This is a contradiction. $\endgroup$
    – Marcus M
    Commented Apr 22, 2021 at 22:28

You must log in to answer this question.