Most probably trangle-free graphs

Abstract

The celebrated Mantel's theorem states that any triangle-free graph on $n$ vertices contains at most $\lfloor n^2/4\rfloor$ edges. It is natural to ask how many triangles must exist in a graph with more than $\lfloor n^2/4\rfloor$ edges--a problem known as the Erdős-Rademacher problem. In this paper, we propose a probabilistic variant of this classic problem. Specifically, given an $n$-vertex graph $G$ with $\lfloor n^2/4\rfloor +i$ ($i>0$) edges, we choose the edges of $G$ independently with probability $p$, and the resulting new graph is triangle-free with a certain probability. Our goal is to maximize this probability by choosing $G$ appropriately. For the case where $G$ has $\lfloor n^2/4\rfloor +1$ edges, we determine the exact maximum probability.

9 pages