Spring 2023

Location:South Building (D) 0-804 "Lóczy Lajos" lecture hall.

Time: Friday 14:15-15:45.

Topic of this semester: Large networks and graph limits

In the last decades it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks: separable elements, with connections (or interactions) between certain pairs of them (the internet, social networks, ecological networks, the brain, chips etc.).

These huge networks pose exciting challenges for the mathematician. Graph Theory (the mathematical theory of networks) has been one of the fastest developing areas of mathematics in the last decades. In traditional graph theoretical problems the whole graph is exactly given, and we are looking for relationships between its parameters or efficient algorithms for computing its parameters. On the other hand, very large networks (like the Internet) are never completely known, in most cases they are not even well defined. Data about them can be collected only by indirect means like random local sampling. Dense networks (in which a node is adjacent to a positive percent of others nodes) and sparse networks (in which a node has a bounded number of neighbors) show a very diverse behavior.

One mathematical tool in their study is the theory of graph limits: structures that represent the limit of a sequence of graphs that are larger and larger and at the same time more and more similar to each other. This theory connects graph theory with analysis, and it will be the main topic of this course.

Familiarity with basic graph theory, linear algebra and probability is a prerequisite. More involved methods from these areas will be explained.

Book manuscript: Large networks and graph limits

Final published version: American Mathematical Society, Providence, RI, 2012

Homeworks:

First homework posted April 13. Homework 1. (pdf)

Second homework posted May 3. Homework 2. (pdf)

Third homework posted May 18. Homework 3. (pdf)

Lecture topics:

March 17.

What to ask about them? Even or odd number of nodes, average degree, connectivity.

How to obtain information about them? F->G->H. From the left: sampling, t(F,G), From the right: maximum cut, statphys.

How to model them? Erdos-Rényi random graphs: G(n,p); Albert-Barabási model.

How to approximate them? By smaller graphs: regularity lemmas; by larger (infinite) graphs: graph limits.

What is a "limit"? "More and more similar." Examples: Complete graphs, cycles, grids...

Reading: Sections 1.1-1.5.


March 24.

Homomorphisms: Definition of hom(F,G), inj(F,G), ind(F,G), hom(F,H) for weighted graph H.

Simple formulas: inj = \sum ind, hom = \sum inj(F/P,G), inverting these formulas by inclusion-exclusion

hom(F_1\cup F_2, G)= hom(F_1,G)hom(F_2,G); hom(F, G_1\cup G_2) = hom(F, G_1)+hom(F, G_2) (F connected).

Examples:

hom(P_k,G) = #walks = A^k\cdot J (notation: A\cdot B = tr(A\T B))

hom(C_k,G) = #closed walks = tr(A^k)

hom(S_k,G) = \sum deg^k

hom(G, K_q) = #colorings

hom(G, K_2+loop)= #independent sets

hom(G, K_2+loops+negative sign) characterizes eulerian graphs

Homomorphism and isomorphism: hom(.,G) and hom(G,.) determine G. Reconstruction conjecture.

Homomorphism densities: Definition of t(F,G) and G(p). Thm (without proof): If t(F,G1) = t(F,G2) for every F, then there is G and p1, p2>0 such that G1 = G(p1) and G2 = G(p2).

Definition of convergence.

Distance of graphs ``the cheap way''; convergence = Cauchy

Reading: Sections 5.2.2, 5.2.3, first half of 11.1.


March 31.

Recall definitions t(F,G), convergence

Examples: half-graphs, random graphs G(n,p) (very similar!)

Distances of graphs

1. Edit distance (only mentioned)

2. Cut distance:

(a) labeled. d_\square(G,G'). Equivalant forms: S=T, S=V\T, (f,g), ...

(b) unlabeled, same number of nodes. \delta^*(G,G') Note: contains isomorphism problem.

(c) unlabeled, possibly different number of nodes: \delta(G,G').

Examples: random graphs, complete and complete bipartite, distance from empty graph

Theorem: (G_n) convergent iff it is Cauchy in unlabeled cut distance

Counting Lemma (proved)

Inverse Counting Lemma (stated)

Reading: Sections 8.1.2, 9.1.1, 9.1.2, 10.5. (The proofs there are formulated for kernels in the book, see Section 9.2.2.)


April 14.

Weak regularity Lemma for linear spaces. This treatment is in my paper with Balázs Szegedy "Szemerédi's Lemma for the Analyst"

Weak regularity lemma for matrices. Frobenius and cut norm of a matrix. Projection of a matrix to a partition. Three forms: (a)approximation by linear combination of rank 1 0-1 matrices, (b) approximation by stepfunctions, (c) approximation by projections. This treatment follows Lemma 9.7 in my other book "Graphs and Geometry" Final published version: American Mathematical Society, Providence, RI, 2019

Weak regularity lemma for graphs.

Original regularity lemma (only sketched, it is not needed in this course).

Graphons: definition, regularity lemma for graphons, counting lemma for graphons (just stated)


April 21.

Construction of the limit graphon.

Main Lemma: Every sequence of graphs whose sizes converge to infinity, has a subsequence that (with appropriate labeling) converges to a graphon W in cut norm.

We use the Regularity Lemma for graphons (Section 9.2), the Counting Lemma for graphons (Section 10.5), and the Martingale Convergence Theorem (Section A.3.6).

Definition: G_n --> W if t(F,G_n) --> t(F,W) for every F. Three main facts:

--- Every convergent sequence of graphs converges to a graphon. (Proved.)

--- Every graphon is the limit of a convergent graph sequence. (To be proved next time.)

--- The limit graphon is uniquely determined up to a measure preserving transformation. (Without proof.)


April 28.

Every graphon is the limit of a convergent graph sequence. W-random graphs.

Examples of convergent graph sequences: half-graphs, random graphs, Paley graphs (edge-density and 4-cycle density computed).

Quasirandom graph characterization (stated, proof postponed).

Cloning sequence: convergent with probability 1, but limit graphon is not determined.


May 5.

Adjacency matrix of a graph and its spectrum. Analogue for graphons: Kernel operator on L^2 associated with a graphon. Spectral decomposition. Cycle densities and specturm.

Application: proof of quasirandom graph characterization.

Extremal graph theory: edge-density vs. triangle density. Goodman's inequality and its proof by a "calculus of formal linear combinations of graphs".

Whether a linear inequality between subgraph densities is valid is undecidable (without proof).


May 19.

Algorithmic applications of graph limits I. Parameter esitmation: approximating f(G) by h(G[X]), where $h$ is a "test parameter", and $X$ is a k-sample from V(G).

Lemma 1. We may always take h=f.

Lemma 2. The following are equivalent: (a) f is estimable; (b) f is uniformly continuous on the metric space of graphs with the cut-metric; (c) for every convergent sequence (G_n), the sequence (f(G_n)) is convergent.

Lemma 3. f is estinable iff (i) for V(G_n)=V(G'_n) such that $d_\square(G_n,G_n')->0, we have f(G_n)-f(G_n')_>0; (ii) f(G(p)) is convergent as p->infinity; (iii) adding an isolated node to G changes f(G) little if $G$ is large.

Examples: (1) t(F,.) is estimable; (2) size of max cut/|V(G)|^2 is estimable.

Algorithmic applications of graph limits II. Property testing

Examples: no edge; max clique >n/2; triangle-free

Reading: Sections 15.1, 15.3


May 26.

Theorem: triangle-freeness is testable. Reformulation: Removal Lemma. Proof via graph limits.

Application in Number theory: the Erdos-Turán problem for 3-term arithmetic prograssions.

A glimpse of other limit theories for combinatorial structures: permutations, hypergraphs.