User:SunshineAllNight/sandbox

In extremal graph theory, Szemerédi’s regularity lemma states that a graph can be partitioned into a bounded number of parts so that the edges between parts are regular. The lemma shows that properties of random graphs can be applied to general graphs like counting the copies of a given subgraph within graphs. Endre Szemerédi proved the lemma over bipartite graphs for his theorem on arithmetic progressions in 1975 and for general graphs in 1978. Variants of the lemma use different notions of regularity and apply to other mathematical objects like hypergraphs.

Preliminaries

model: g(20, 0.4) number of expected edges = ((20)(21)/2)0.4 = 84

edge density: 84/(14)(15) = 0.4

Random graphs

((A graph is a mathematical object with vertices and edges, where an edge connects two vertices.))

Random graphs are constructed using probabilistic processes. The main notion of a random graph in graph theory is the Erdős-Rényi model $G(n,p)$, defined as a graph having $n$ vertices and probability $p$ for any edge to be in the graph, independently from all other edges. For example, instances of $G(20,0.4)$ will have ${\frac {20\cdot 21}{2}}\cdot 0.4=210\cdot 0.4=84$ edges on average. (Add footnote on this method of calculation, triangular numbers = max number of edges on a graph)

Random graphs are useful in modelling general graphs because they have properties that general graphs do not have. For example, the excepted number of copies for the triangle graph $K_{3}$ in $G(n,p)$ is ${n \choose 3}p^{3}$ and more generally the excepted number of copies for complete graphs $K_{a}$ on $a$ vertices is ${n \choose a}p^{a \choose 2}$.

(cite calculations, make it more detailed, take both from stackexchanges ((https://cs.stackexchange.com/questions/2118/number-of-clique-in-random-graphs https://math.stackexchange.com/questions/730294/expected-number-of-triangles-in-a-random-graph-of-size-n)), find on textbooks, use footnote to explain proofs)

Edge density

In a graph, its vertex set $V$, and disjoint subsets $X$ and $Y$ of $V$, the edge density of two disjoint subsets is defined as:

For example, if $C$ has 14 vertices and $D$ has 15 vertices with 84 edges with an end in each subset, the edge density of $C,D$ would be ${\frac {E(C,D)}{|C||D|}}={\frac {84}{14\cdot 15}}={\frac {84}{210}}=0.4$.

ε-regularity

connect to random graph model

Jensen’s inequality

connect to convexity

Partitioning with different notions of regularity

Applications