Introduction and Motivation: Graph Limits and Homomorphism Density Inequalities
Motivation: Graph limits are used to solve graph inequalities problems, namely minimum/maximum subgraph densities for a given edge density.
Today's focus: Understanding the connection between potential subgraphs or homomorphism densities within a large graph is possible through the use of homomorphism density inequalities.
Mantel's theorem and Turan's theorem serve as early examples of connections to earlier theorems.
Reiterating Mantel's theorem, triangle density cannot be zero if edge density is greater than 1/2.
- Generalisation: According to Turan's theorem, the edge density is no more than 1 - 1/R if the K R + 1 density is zero.
- The objective is to fully comprehend the set of feasible edge versus triangle densities.
Edge vs. Triangle Density: The Feasible Region D23
Visualisation: Triangle density on the y-axis, edge density on the x-axis, with the goal of identifying the set of viable points inside the unit square.
The horizontal line at zero density is located in the area below edge density 1/2, according to Mantel's theorem.
A compact region is the set of potential densities (D23).
Compactness results from the continuity of densities under cut distance and the compactness of the graphon space under the cut metric.
There are no missing points up to measure zero, indicating that the region is closed.
Finding the highest and lowest feasible triangle densities (upper and lower boundaries) for a given edge density is the equivalent question.
Determining the Upper Boundary
Simpler approach: Find the highest triangle density that can be achieved with a specific edge density.
It is intuitive to group edges into a clique in order to maximise triangles for a specific number of edges.
- Graphons corresponding to a clique reach the upper boundary.
- The triangle density for a graphon that corresponds to a clique structure with edge density x is y. y = x^(3/2) is the curve.
- Because the set of graphs is dense in the space of graphons, the proof approach is adequate to establish the inequality for graphs.
Graph inequality: A graph's K3 density is, at most, the K2 density multiplied by three.
Triangle densities and edge densities correlate to counting closed walks, as demonstrated by the spectral method.
Closed walks of length three are related to K3 homomorphisms.
- Tool: Spectral moment - counting closed walks entails examining the adjacency matrix's eigenvalue powers.
- Power Mean Inequality: The sum of t-powers is less than or equal to the t-power of the sum (normalised) for positive t and non-negative reals.
- The K2 density is related to the sum of squares of the eigenvalues.
For graph homomorphisms, the inequality is true; for densities, the inequality is obtained by dividing by V^3.
The speaker finds this proof less intuitive for a "physical" inequality because it is spectral ("frequency" domain) rather than purely physical. Although it goes "beyond the physical domain," it is accurate.
Limitation: Without additional effort, this spectral proof is not directly applicable to K4 or general KR.
Cauchy-Schwarz Inequality
An alternative proof of the upper bound that remains in the "physical" realm.
For symmetric measurable functions from the unit square to R, this proves a slightly stronger statement.
- Inequality: The pointwise square of the K2 density of W raised to the power of three halves is the upper bound of the K3 density of W.
- Cauchy-Schwarz inequality is applied repeatedly as the method.
Steps for application:
- K3 density should be expressed as an integral.
- Use Cauchy-Schwarz to split terms involving x with respect to dx.
- Use Cauchy-Schwarz to split terms involving y and apply it to dy.
- Split the remaining terms by applying Cauchy-Schwarz with regard to dz.
Result: The product of L2 norms of W bounded the integral.
Connection to Holder's inequality: When functions rely on particular sets of variables, this is a more robust form of Holder's inequality. A stronger bound than L3 norms is obtained by using L2 norms (on a probability measure space).
The Kruskal-Katona Theorem and Graph Theoretic Proof
Is there a proof that is solely based on graph theory?
Kruskal-Katona Theorem
Kruskal-Katona theorem: The maximum number of triangles for a given number of edges is stated by a more exact combinatorial result.
Kruskal-Katona explains in detail how to build a graph that maximizes triangles by creating a structure resembling a clique.
The proof method for Kruskal-Katona involves:
- Using a combinatorial shifting or compression argument
- Transforming a graph into a clique-like structure while maintaining edges
- Increasing triangles through this transformation
Bollobás's Theorem: Determining Linear Inequalities on Clique Densities
Theorem assertion: If and only if it holds for all cliques, then a linear inequality involving clique densities holds for all graphs.
Importance: It is much simpler to determine whether such an inequality holds true for all graphs if you only look at cliques.
A Proof Sketch
It is trivial to go in one direction:
- If it holds for all graphs, then it holds for cliques.
- The alternative direction requires demonstrating it for every graphon.
Examine node-weighted simple graphs, which are a dense subset of graphons.
Select a minimal counterexample for a node-weighted graph H, assuming that the inequality fails.
Demonstrate that all node weights must be positive for this minimal H; if not, remove the node and reduce the number of nodes.
Show H must be a complete graph (clique). Because cliques don't have repeated vertices, the clique density expression is multilinear in node weights.
- The linear expression must be minimized at the boundaries.
- Weights must be equal since minimalism requires that they be non-zero.
This proves the theorem by defying the presumption that the inequality fails for a minimal counterexample.
Outcomes of Bollobás's Theorem and the Feasible Region
Extreme points of the convex hull of the set of clique densities over all graphons are provided exactly by the points corresponding to simple cliques Km for all M=1, 2,....
An example of edge versus triangle density (n=3) for Km, the extreme points are (K2 density, K3 density).
Points are equivalent to (M choose 2 / M choose 2, M choose 3 / M choose 3); this is (1, 1) for M>=3 and (1, 0) for M=2, and (0, 0) for M=1.
Reinterpretation using the illustration as a guide: In addition to Km densities in general graphs, the extreme points displayed are probably associated with complete graphs or Turán graphs.
For M=2,3,4..., the correct points are (0,0), (1/2,0), and a series of points (2/3,2/9), (3/4,3/8), etc.
Let's adhere to the points as stated in the source:
- For W = K_M, the extreme points have the form (K2 density, K3 density).
- Points (1/2, 0), (2/3, 2/9), (3/4, 3/8), and so on are displayed in Figure 13.
The statement "extreme points they are of the form mus1 / m -1 m - 2 / m 2 for positive integers m" should be read again.
The **lower boundary of the convex hull of the feasible region** is formed by these points.
The convex hull information allows for the deduction of Turán's theorem.
- Mantel's theorem implies no feasible points beyond edge density 1/2 on the zero triangle density line.
- Other constraints are implied by the region's confinement within the convex hull.
The convex hull implies a lower curve for triangle density given edge density, which is y = 2x - 1.
The Whole Viable Area D23
We now fully understand the actual region. The upper curve (y = x^(3/2) from clique-like structures) and a series of concave curves or scallops from below form its boundaries.
Using a method known as Flag Algebra, Razborov produced the challenging result of the lower curve.
Flag Algebra is a computerized technique for proving graph theoretic inequalities.
- It frequently entails computer computation and semi definite programming.
Razborov's Theorem
Lower curve: A node-weighted complete graph (k-click), where k-1 node weights are equal and the last is smaller, achieves the minimum triangle density for a fixed edge density between two specific points.
The minimizer construction for intermediate edge densities is not unique, in contrast to Turan's theorem. This non-uniqueness complicates the minimization problem.
Extensions of the Result
- Nikiforov (K4) and Razborov (KR) extended the result to KR densities.
- Scallops are portrayed visually as being somewhat "cartoon"; in reality, the concavity is subtle.
Decidability of Graph Homomorphism Inequalities
Linear inequalities of densities are frequently used to express polynomial graph inequalities. Is it possible to determine if a given graph homomorphism inequality is true?
Background: Polynomial Inequalities' Decidability
- Decidable over real numbers (Tarski's theorem). According to Artin's theorem, positiveness is related to the sum of squares of rational functions.
- Over integers: Not decidable (Matiyasevich's theorem on Diophantine equations, Hilbert's 10th problem).
- Which is the decidability of graph inequality closer to: integers or reals? The fact that graphons have real weights suggests that they are similar to reals.
Outcome: Inconclusive (Hatami and Norin). The discreteness of points on the lower curve is the reason. By limiting to particular graph constructions that correspond to these discrete points, the problem can be reduced to determining integer inequalities.
Open Problems: Sidorenko's Conjecture
Although there is general indecision, certain issues are noteworthy:
- Sidorenko's conjecture: When a graph H is bipartite, its H density in any graph G (or graph on W) is at least equal to the edge density of G (or W) multiplied by the number of edges in H.
- This is true in quasi-randomness for H=C4 (4-cycle).
- There are no known counterexamples, so the conjecture is open.
- The Mobius strip graph (K5,5 minus a 10-cycle) is the first open case. Whether Sidorenko's inequality applies to this particular graph is unknown.
- It is believed that the term "Mobius strip" refers to the face-vertex incidence graph of the simplicial complex for a Mobius strip.
Epsilon Error in Graph Homomorphism Inequalities
Although general graph homomorphism inequalities cannot be decided, they can be decided up to an epsilon error.
- There is an algorithm based on the counting lemma and the weak regularity lemma.
- An epsilon-regular partition can be used to encode density data. It is sufficient to check the inequality on weighted graphs with a bounded number of parts, where the edge weights are multiples of epsilon.
- According to the regularity lemma, the number of possibilities to check is finite.
Conclusion
Examined a number of general findings and graph theoretic inequalities. There are still many unsolved issues with graph homomorphism inequalities.
- The section on extremal graph theory is now complete; the following section will cover Roth's theorem and its Fourier analytic proof.
-1.png)
-1.png)