[next] [prev] [prev-tail] [tail] [up]

2 Hypergraph regularity

Proposition 2.1. Let X,Y,Z be sets and let f:X×Y×Z→[−1,1] be a function. Then the following are equivalent:

  • (i) 𝔼x0,x1∈X𝔼y0,y1∈Y𝔼z0,z1∈Z∏⁡(i,j,k)∈{0,1}3f(xi,yj,zk)≤c1.
  • (ii) |𝔼x∈X,y∈Y,z∈Zf(x,y,z)u(x,y)v(x,z)w(y,z)|≤c2 for any u:X×Y→[−1,1], v:X×Z→[−1,1], w:Y×Z→[−1,1].
  • (iii) For any tripartite graph G on X∪Y∪Z, the average of f restricted to △(G):triangles in G is at most c3 in absolute value.

The objects we count in (i) are octahedra:

PIC

Proof. Omitted (but the proof is the same as the proof of Proposition 1.5, only with more Cauchy Schwarzing). □

Definition 2.2. Say f:X×Y×Z→[−1,1] is 𝜀-quasirandom if it satisfies Proposition 2.1(i) with c1=𝜀8. A 3-partite 3-uniform hypergraph H on X∪Y∪Z of density δ is 𝜀-quasirandom if f(x,y,z)=𝟙H(x,y,z)−δ is 𝜀-quasirandom.

Proposition 2.3. Let Hbe a 4-partite 3-uniform hypergraph on vertex set X∪Y∪Z∪W. Suppose H(X,Y,Z),H(X,Z,W),H(X,Y,W),H(Y,Z,W) are all 𝜀-quasirandom of densities δXYZ,δXZW,δXYW,δYZW respectively. Then

|𝔼x,y,z,w𝟙H(x,y,z)𝟙H(x,y,w)𝟙H(x,z,w)𝟙H(y,z,w)−δXYZδXYWδXZWδYZW|≤10𝜀.

PIC

Proof. Omitted (see Example Sheet). □

But this notion is too strong to facilitate a regularity lemma.

Example 2.4. Let G be a random tripartite graph on X∪Y∪Z of edge density 12. Let H be the 3-uniform hypergraph consisting of all triangles in G. The edge density of H is 18. The proportion of octahedra: (12)12. But, if H were quasirandom, we would expect (12)8.

Not only does H fail to be quasirandom, so does any induced subhypergraph.

Example 2.5. Let G be a tripartite graph X∪Y∪Z with each part G(X,Y),G(X,Z),G(Y,Z) quasirandom, of edge density δXY,δXZ,δYZ respectively. Let H be a random hypergraph chosen with ℙ=δ from the 3-hypergraph formed by △(G).

PIC

Then the expected number of octahedra in H is

(δXYδXZδYZ)4δ8|X|2|Y|2|Z|2.

Definition 2.6. Let G be a 3-partite graph on vertex set X∪Y∪Z, and let f:X×Y×Z→[−1,1] be a function supported on △(G). We say f is 𝜀-quasirandom relative to G if

𝔼x0,x1∈Xy0,y1∈Yz0,z1∈Z∏(i,j,k)∈{0,1}3f(xi,yj,zk)≤𝜀8(δXYδXZδYZ)4.

Let H be a 3-partite 3-uniform hypergraph on X∪Y∪Z, and suppose H⊆△(G), |H|=δ|△(G)|. We say H is 𝜀-quasirandom relative to G if

f(x,y,z)={𝟙H(x,y,z)−δif (x,y,z)∈△(G)0otherwise

is 𝜀-quasirandom relative to G.

Proposition 2.7. Let G be a 4-partite graph on X∪Y∪Z∪W with all six bipartite parts 𝜀-quasirandom. Let f:X×Y×Z→[−1,1], g:X×Y×W→[−1,1], h:X×Z×W→[−1,1], k:Y×Z×W→[−1,1], all supported on △(G). Suppose that f is η-quasirandom relative to G(X,Y,Z). Then provided 𝜀14≤2−38(ηδ)8,

|𝔼x,y,z,wf(x,y,z)g(x,y,w)h(x,z,w)k(y,z,w|≤2ηδ,

where

δ:=δXYδXZδXWδYZδYWδZW.

Note that this proposition is much easier to prove if we use the much stronger notion of quasirandomness that was introduced at the beginning of this section.

Notation.

δZW=|G(Z,W)||Z||W|δYZW=number of triangles in G(Y,Z,W)|Y||Z||W|δY(x,x′)=number of y∈Y such that x∼y, x′∼y|Y|δZW(x,x′)=number of edges zw in G(Z,W) such that x∼z, x∼w, x′∼z, x′∼w|Z||W|

Proof.

|𝔼y,z,wk(y,z,w)𝔼xf(x,y,z)g(x,y,w)h(x,z,w)|8≤(𝔼y,z,wk(y,z,w)2)4(𝔼y,z,w|𝔼xf(x,y,z)g(x,y,w)h(x,z,w)|2)4≤δYZW4(𝔼x,x′𝔼y,z,wfx,x′(y,z)⏟f(x,y,z)f(x′,y,z)gx,x′(y,w)hx,x′(z,w))4≤δYZW4𝔼x,x′(𝔼y,z,wfx,x′(y,z)gx,x′(y,w)hx,x′(z,w))4=δYZW4𝔼x,x′(𝔼z,whx,x′(z,w)𝔼yfx,x′(y,z)gx,x′(y,w))4

So far, we haven’t done anything difficult, but the first tricky step comes now. It will be important that we do not (immediately) separate hx,x′(z,w) from the rest of the expression, because it will be important that we use the fact that hx,x′(z,w) is only supported on triangles of G.

δYZW4𝔼x,x′(𝔼z,whx,x′(z,w)𝔼yfx,x′(y,z)gx,x′(y,w))4=δYZW4𝔼x,x′(𝔼z,whx,x′(z,w)𝟙G(z,w)𝔼yfx,x′(y,z)gx,x′(y,w))4≤δYZW4𝔼x,x′(𝔼z,whx,x′(z,w)2)2(𝔼z,w𝟙G(z,w)(𝔼yfx,x′(y,z)gx,x′(y,w))2)2≤δYZW4𝔼x,x′δZW(x,x′)2(𝔼y,y′𝔼z,wfx,x′,y,y′(z)⏟:=fx,x′(y,z)fx,x′(y′,z)gx,x′,y,y′(w)𝟙G(z,w))2≤δYZW4𝔼x,x′δZW(x,x′)2(𝔼y,y′𝔼wgx,x′,y,y′(w)𝔼zfx,x′,y,y′(z)𝟙G(z,w))2=δYZW4𝔼x,x′δZW(x,x′)2(𝔼y,y′𝔼wgx,x′,y,y′(w)𝟙G(x,q)𝟙G(x′,y)𝟙G(x,y′)𝟙G(x′,y′)𝔼zfx,x′,y,y′(z)𝟙G(z,w)⏟=𝔼y,y′∏𝟙G(x,y)𝔼z,wfx,x′,y,y′(z)gx,x′,y,y′(w)𝟙G(z,w))2≤δYZW4𝔼x,x′δZW(x,x′)2(𝔼y,y′∏𝟙G)(𝔼y,y′|𝔼z,wfx,x′,y,y′(z)gx,x′,y,y′(w)𝟙G(z,w)|2)=δYZW4𝔼x,x′δZW(x,x′)2δY(x,x′)2𝔼y,y′(𝔼wgx,x′,y,y′(w)𝟙G(w,x)𝟙G(w,x′)𝟙G(w,y)𝟙G(w,y′)𝔼zfx,x′,y,y′(z)𝟙G(z,w))2≤δYZW4𝔼x,x′δZW(x,x′)2δY(x,x′)2𝔼y,y′(𝔼w𝟙ug(w,x)𝟙G(w,x′)𝟙G(w,y)𝟙G(w,y′)⏟=:δW(x,x′,y,y′))𝔼w|𝔼zfx,x′,y′,y′(z)𝟙G(z,w)|2=𝔼x,x′,y,y′,z,z′fx,x′,y,y′,z,z′⏟fx,x′,y,y′(z)fx,x′,y,y′(z′)ϕ(x,x′,y,y′,z,z′)=𝔼x,x′,y,y′,z,z′F(x,x′,y,y′,z,z′ϕ(x,x′,y,y′,z,z′)=⟨F,ϕ⟩

where

ϕ(x,x′,y,y′,z,z′)=δYZW4δZW(x,x′)2δY(x,x′)2δW(x,x′,y,y′)δW(x,x′,y,y′,z,z′)F(x,x′,y,y′,z,z′)=fx,x′,y,y′,z,z′

PIC

Note that ϕ only depends on the underlying graph, which we assumed was 𝜀-quasirandom. We can compute

𝔼x,x′,y,y′,z,z′ϕ(x,x′,y,y′,z,z′)=(δYZδYZδZW)4⋯=(δXYδYZδXZ)4(δXWδYWδZW)8=:𝜃.

Want to show:

⟨uf,ϕ⟩≈⟨F,𝜃⟩=𝜃⟨F,1⟩⏟≤η8(δXYδXZδYZ)4.

Claim 2.8. Suppose 238𝜀14≤σ𝜃. Then ϕ(x,x′,y,y′,z,z′) differs from 𝜃 by more than σ𝜃 for at most a σ𝜃-proportion of (x,x′,y,y′,z,z′)∈X2×Y2×Z2.

Proof: See Example Sheet 1.

Let σ=η8(δXYδXZδYZ)4. Call (x,x′,y,y′,z,z′) bad if |ϕ(x,x′,y,y′,z,z′)−𝜃|>σ𝜃, and good otherwise. Let

ϕ~(x,x′,y,y′,z,z′)={ϕ(x,x′,y,y′,z,z′)if (x,x′,y,y′,z,z′) is good𝜃otherwise

By the claim, ∥ϕ−ϕ~∥1≤2σ𝜃 and ∥ϕ~−σ∥∞≤σ𝜃, and also ∥F∥1≤1, ∥F∥∞≤1. Hence

|⟨F,ϕ⟩−⟨F,𝜃⟩|≤|⟨F,ϕ−ϕ~⟩|+|⟨F,ϕ~−𝜃⟩|≤∥F∥∞∥ϕ−ϕ~∥1+∥F∥1∥ϕ~−𝜃∥∞≤3σ𝜃=3η8⋅δ8

But

|⟨F,𝜃⟩|≤𝜃η8(δXYδXZδYZ)4=η8⋅δ8

so

|𝔼x,y,z,wf(x,y,z)g(x,y,w)h(x,z,w)k(y,z,w)|8≤|⟨F,ϕ⟩|≤|⟨F,ϕ⟩|+3η8δ8≤4(ηδ)8.□

Corollary 2.9 (Simplex counting lemma). Let G be a 4-partite graph on X1∪X2∪X3∪X4, with all six bipartite graphs 𝜀-quasirandom of densities δij respectively. Let Hijk be a 3-partite 3-uniform hypergraph on Xi∪Xj∪Xk which is η-quasirandom relative to △(G(Xi,Xj,Xk)), of relative density δijk. Let H=H123∪H134∪H124∪H234. Then

|𝔼x1,x2,x3,x4𝟙H(x1,x2,x3)𝟙H(x1,x2,x4)𝟙H(x1,x3,x4)𝟙H(x2,x3,x4)−∏δijk∏δij|≤8η∏δij.

Proof. Let

f(x1,x2,x3)=𝟙H(x1,x2,x3)−δ123𝟙G(x1,x2)𝟙G(x1,x3)𝟙G(x2,x3)t

and consider

𝔼x1,x2,x3,x4f(x1,x2,x3)𝟙H(x1,x2,x4)𝟙H(x1,x3,x4)𝟙H(x2,x3,x4).

By Proposition 2.7, this is at most 2η∏⁡δij (in absolute value). Iterate. □

Definition 2.10 (Relative msd). Let U be a set, let f:U→ℝ, and let U=B1∪B2∪⋯∪Br be a partition of U. Then the mean square density (msd) of f relative to this partition is

∑i=1r|Bi||U||𝔼x∈Bif(x)|2.

Lemma 2.11. Let U be a set, f,g:U→[−1,1], U=B1∪B2∪⋯∪Br. Suppose g is constant on each Bi. Then the mean square density of f relative to the partition is ≥⟨f,g⟩2∥g∥22.

Definition 2.12. Let G be a 3-partite graph on X∪Y∪Z, and suppose that G(X,Y), G(X,Z), G(Y,Z) are partitioned into ⋃⁡iGi(X,Y), ⋃⁡jGj(X,Z), ⋃⁡kGk(Y,Z), respectively. For each (x,y,z)∈△(G), let its index be the triple (i,j,k) such that xy∈Gi(X,Y), xz∈Gj(X,Z), yz∈Gk(Y,Z).

The induced partition of △(G) is the partition of triples in △(G) according to their index.

[A typical cell of this partition looks like △(Gi(X,Y)∪Gj(X,Z)∪Gk(Y,Z)).]

If f:X×Y×Z→[−1,1], then the msd of f relative to the partitions ⋃⁡iGi(X,Y), ⋃⁡jGj(X,Z), ⋃⁡kGk(Y,Z) is defined to be the msd of f relative to the induced partition.

Lemma 2.13. Let G be a 3-partite graph on X∪Y∪Z with bipartite parts of densities δXY,δXZ,δYZ, respectively. Let δ=δXYδXZδYZ, and suppose all bipartite parts are 𝜀-quasirandom. Let H be a 3-partite 3-uniform hypergraph on X∪Y∪Z, and let the relative density of H in △(G) be γ. Suppose 221𝜀<δ7, and suppose H is not η-quasirandom relative to △(G). Then there are partitions G(X,Y)=G1(X,Y)∪⋯∪Gl(X,Y), G(X,Z)=G1(X,Z)∪⋯∪Gm(X,Z), G(Y,Z)=G1(Y,Z)∪⋯∪Gn(Y,Z) relative to which the msd of H is ≥γ2+2−11η16. Moreover, l,m,n≤33δ−2.

Proof. Let

f(x,y,z)=(𝟙H(x,y,z)−γ)𝟙G(x,y)𝟙G(x,z)𝟙G(y,z).

The hypothesis amounts to

𝔼x,x′,y,y′,z,z′fx,x′,y,y′,z,z′≥η8δ4.(†)

For each (x,y,z)∈△(G), let

Fxyz(x′,y′,z′)=fx,x′,y,y′,z,z′f(x′,y′,z′)

and let

F(x′,y′,z′)=𝔼x,y,zFxyz(x′,y′,z′).

Then (†) becomes

𝔼x,x′,y,y′,z,z′Fxyz(x′,y′,z′)f(x′,y′,z′)=𝔼x,y,z⟨⏟𝔼x′,y′,z′f,Fxyz⟩.

Note that each of the Fxyz can be written as a product

u(x′,y′)v(y′,z′)w(x′,z′),

where each of u,v,w→[−1,1].

For each (x,y,z)∈△(G) and each pair (x′,y′), define ũ(x′,y′) as follows:

Same for v,w.

Finally, let

F~xyz(x′,y′,z′)=ũ(x′,y′)ṽ(x′,z′)w~(y′,z′),

and observe that the expectation (in the random choices of ũ,ṽ,w~ described above) of F~xyz(x′,y′,z′) is Fxyz(x′,y′,z′). Let F~(x′,y′,z′)=𝔼x,y,zF~xyz(x′,y′,z′). Since the expectation of ⟨f,F~xyz⟩ equals ⟨f,Fxyz⟩, we can make random choices so that ⟨f,F~⟩≥η8δ4 (so from now on, “expectation” no longer refers to expectation over the possible random choices of ũ,ṽ,w~).

Let r≥δ−2, choose F~1,…,F~r at random from F~xyz and let D=1r∑⁡i∈[r]F~i. For each i∈[r], the expectation of ⟨f,F~i⟩ is at least 1δXYZ⟨f,F~⟩, where δXYZ=|△(G)||X||Y||Z|. So the expectation of ⟨f,D⟩ is at least ≥η8δ4δXYZ. By Counting Lemma, and the upper bound on 𝜀, δ2≤δXYZ≤2δ. So the expectation of ⟨f,D⟩ is at least η8δ2δXYZ⋅δ2≥η8δ24δXYZ.

Note that

∥F~∥22=𝔼x′,y′,z′|𝔼x,y,zF~xyz(x′,y′,z′)|2≤𝔼x′,y′,z′|𝔼x,y,z𝟙K2,2,2⏟as a graph(x,x′,y,y′,z,z′)|2=𝔼x′,y′,z′𝔼x1,y1,z1x2,y2,z2𝟙K2,2,2(x1,x′,y1,y′,z1,z′)𝟙K2,2,2(x2,x′,y2,y′,z2,z′)

PIC

So we are counting a 3-partite graph on X∪Y∪Z with 3 vertices in each part and 7 edges between each part.

By a generalisation of Counting Lemma and the upper bound on 𝜀, ∥F~∥22≤2δ7≤16δ4δXYZ3, since δ2≤δXYZ. By Example Sheet 1 Problem 11, the expectation of ∥D∥22 is at most 2δXYZ−2∥F~∥22≤32δ4δXYZ, provided r≥δ−2. Hence the expectation of 256δ2⟨f,D⟩−η8∥D∥22 is at least 32η8δ4δXYZ. It follows that there is a choice of F~1,…,F~r such that

⟨f,D⟩≥η8δ2δXYZ8

and ∥D∥22≤256δ2η−8⟨f,D⟩. For such D,

⟨f,D⟩∥D∥22≥η8δ2δXYZ8⋅28δ2η−8⟨f,D⟩⏟≤δXYZ≥η16211.□

Definition 2.14. An r-partite chain is a (G,H), where G is an r-partite graph, H an r-partite hypergraph on the same vertex set as G and H⊆△(G). Let ψ(η,δ) be a polynomial in η and δ which vanishes when either is 0.

A 4-partite chain (G,H) is (η,ψ)-quasirandom if

  • All four 3-partite parts of H are η-quasirandom relative to G

  • all six bipartite parts of G are ψ(η,δ)-quasirandom, where δ is the product of the densities of the bipartite parts of G. Shall use this with ψ(η,δ)=(2−38η888)32.

Remark. We call it a chain because when generalised to 4-uniform, 5-uniform etc, we would use (G,H,K,…) rather than (G,H).

Definition 2.15. Let X1,X2,X3,X4 be four sets. Then a decomposition of the complete 4-partite graph K(X1∪X2∪X3∪X4) consists of the following:

  • For each Xi a partition into subsets Xi(1)∪⋯∪Xi(ni).

  • For each K(Xi∪Xj), a partition into subgraphs

    Gij(1)∪⋯Gij(mij).

A typical graph G in this decomposition will have vertex sets Xi(r),Xj(s),Xk(t) and edge set

Gij(u)(Xi(r)∪Xj(s))∪Gij(v)(Xi(r)∪Xk(t))∪Gjk(w)(Xj(s)∪Xk(t)).(†)

PIC

Given a 4-partite 3-uniform hypergraph H on X1∪X2∪X3∪X4, we obtain an induced 3-partite 3-uniform hypergraph on Xi(r)∪Xj(s)∪Xt(t) with edges given by E(H)∩△(†).

The pair (G,H) is a chain. The associated chain decomposition (ACD) of H is the set of all chains arising from a given decomposition.

Definition 2.16. Let H be a 4-partite 3-uniform hypergraph on X1∪X2∪X3∪X4, and suppose we have a decomposition of K(X1∪X2∪X3∪X4). Then the associated chain decomposition of H(Xi∪Xj∪Xk) is said to be (𝜀,η,ψ)-quasirandom if for all but 𝜀|Xi||Xj||Xk| edges (xi,xj,xk), the associated tripartite chain in which (xi,xj,xk)lies is (η,ψ)-quasirandom. The associated chain decomposition of H is (𝜀,η,ψ)-quasirandom if all four parts (e.g. H(X1∪X2∪X3)) are.

PIC

Theorem 2.17. Let H be a 4-partite 3-uniform hypergraph on X∪Y∪Z∪W, and let 𝜀,η>0. Then there is a decomposition of K(X∪Y∪Z∪W) such that the associated chain decomposition of H is (𝜀,η,ψ)-quasirandom. Moreover the number of bipartite graphs in the decomposition is bounded by a function of 𝜀 and η only, and the number of sets in the partitions of X,Y,Z,W depends on 𝜀,η,ψ.

[next] [prev] [prev-tail] [front] [up]