2 - Isoperimetric Inequalities Flashcards
(21 cards)
What is a Hamming Ball on Qn?
This is where we take all layers from the bottom to the rth and then take a subset in the (r+1)th layer. Often This set will be a ball, but not always.
Let G be a graph. Define the boundary of A<V(G)
Define the neighbourhood if A.
Define an Isoperimetric inequality for a graph.
b(A)={x in V(G) : x is not in A, but xy is an edge of G for some y in A}
So the boundary of a sun graph is the set of vertices one edge away from the subgraph.
The Neighbourhood of a graph is:
N(A)=b(A) U A,
So is all things at distance at most one from A.
This is a statement of the form:
Or all A=f(|A|)
So roughly, it tells us how tightly we can pack a set into G.
What is the simplicial ordering on Qn?
Two sets x, y in Qn are ordered in symplicial ordering if x<y if it is on a lower layer than y, or if it is on the same layer and below y in the Lexicographic ordering.
For A<Qn, define the i-sections of A, where i is an integer between 1 and n.
What is the corresponding i-compression of A?
When is A i-compressed?
The i-sections of A are the two families A(i,+), A(i,-) where the first is all subsets of P(X-i) obtained from removing i from some set x in A, and the second is all subsets of P(X-i) which are already in A.
The i-compression of A is Ci(A)<Qn defined by the two i-sections:
Ci(A)(i,+)=the first |A(i,+)| elements of simplicial on P(X-i)
Ci(A)(i,-)=the first |A(i,-)| elements of simplicial on P(X-i)
A is i-compressed if Ci(A)=A.
What is Harpers theorem?
Prove it.
For A=2.
CLAIM: taking an i-compression reduces the neighbourhood
Proof:
Let B=Ci(A)
Then prove that for any A<Qn by setting A=A0 and if we have defined Ak then if it is i-compressed for all i, then stop. Otherwise, choose an i such that Ak is not i-compressed and let Ak+1be Ci(Ak). This terminates, since the sum of the positions in simplicial of all sets in Ak decreases each time.
Now, we have B=Ak when the sequence stops, and B is I-compressed for all i, has the same size as A and has a smaller neighbourhood.
If B is not an initial segment of simplicial, then we can show it is one if two things, depending on whether or not n is even. In each case, the neighbourhood of B is clearly greater than that of C, for an initial segment of simplicial, C. And so we are done.
Use Harpers theorem to prove Kruskal-katana
So, we prove that Lex is best for upper shadow, since this is equivalent to Colex best for lower shadow.
Now, if B<(r+1)Uδ+(Β) where obviously replace B with C for the other one. So that, we see the upper shadow of C is less than that of B. Done!
For A=Σ(nCi) where the sum is from 0 to r?
The t-neighbourhood of A is:
N(t,A)=the set of x in Qn which are at most distance t away from A, where distance is defined in graph sense.
Well, by induction:
|N(t,A)|>=Σ(nCi) where now we sum from 0 to r+t.
Find a bound for Σ(nCi) where we sum from 0 to the largest integer less than (1/2-ε)•n. This bound should be exponentially small.
Use this bound to prove that a half set of Qn has ‘exponentially big εn neighbourhoods’
Firstly show that for i
When is a function f :Qn–> R lipschitz?
What is a Levy mean or median for f?
When |f(x)-f(y)|==M}|>=1/2•|Qn|
& |{x in Qn : f(x)=1/2•|Qn|
Prove the following theorem:
0=1-(4/ε)•e^(-ε^2•n/2)
What does this mean?
Firstly, this theorem states that if we have a “well behaved” function on Qn, then it is almost constant everywhere.
To prove it, use the fact that M is a Levy mean and so the sets of x with f(x) less than (and greater than) M are Half sets. So we can apply our εn neighbourhood bound, which gives these large, and this gives result.
For a graph G, define the diameter of G.
What is α(G,ε) for some small ε>0?
So if this is small then what does this say about 1/2-sized sets?
D=max{d(x,y) : x,y in G}
α(G,ε)=max{1-|A(εD)|/|G| : A=1/2}
If this is small then 1/2-sized sets have large εD-neighbourhoods.
Define a Levy Family.
What example have we already seen?
What converse to this do we have?
Proof?
A levy family is a sequence of graphs G1,G2,… with α(Gn,ε) tending to zero as n tends to infinity for any ε>0.
Qn is a levy family because half seized sets have exponentially big εn-neighbourhoods.
Let G be a graph such that for every lipschitz function f : G—>R with median M, and
|{x in G : |f(x)-M|==1-α for some fixed α,t. Then for A=1-α
Proof:
Define a function f : G –> R
x |—-> d(x,A)
then f is lipschitz with 0 as a median, as A is half sized set. But At={x in G : f(x)=<t}
Define the edge boundary of A<G for G a graph.
Define the binary ordering on Qn.
This is
δΑ={xy in E(G) : x in A, y not in A}
Binary ordering on Qn:
x<y if max(xΔy) is in y.
Define the i-Binary compression of A<Qn.
For 1<i><Qn by the i-sections:
Bi(A)(i,+)= first |A(i,+)| elements of binary on P(X-i)
Bi(A)(i,-)= first |A(i,-)| elements of binary on P(X-i)</i>
What is the edge Isoperimetric inequality in the cube?
Prove.
For any A1. Fix an i. Claim: |δBi(A)|=<Qn is i-binary compressed for all i and is not an IS of binary, then it is just the subcube P([n-1]) after taking the inal point out and adding in the point n. This does it.
Define the Isoperimetric number of a graph.
What does it tell us?
What is i(Qn)?
The Isoperimetric number of a graph is:
i(G)=min{|δΑ|/|A| : A=1. Hence i(Qn)=1.
Define the grid [k]^n.
Define the simplicial ordering on [k]^n
The grid [k]^n is the graph with vertex set
[k]^n = {(x1,…,xn) : 1yi where i is the minimal j where xj isn’t yj.
(Note: |x| is the sum of all its coordinates)
For A< [k]^n define the i-sections of A.
For A< [k]^n the i-sections of A are the set of A(1,i),…,A(k,i) < [k]^(n-1. Given by:
A(t,i)={(xi) in [k]^(n-1) :
(x1,…,t,…,xn-1) is in A}
Slogan - the i-sections of A are the elements in the grid [k]^n-1 taken by deleting the ith component of elements in A.
Define the i-compression of A<[k]^n
The i-compression of A< [k]^n is defined by giving its i-sections:
Ci(A)< [k]^n has i-sections:
Ci(A)(t,i) is the initial segment of simplicial on [k]^n-1 of same size as A(t,i)
State and prove the vertex-Isoperimetric inequality on the grid.
Statement:
A< [k]^n, then of C is the IS of simplicial ordering on [k]^nof same size as A, then the neighbourhood of A is greater than that of C
Or, simplicial ordering minimises neighbourhoods.
Proof (sketch)
Induction on n. n=1 is easy.
n>=2.
First prove that taking i-compressions reduces neighbourhood. To do this just work out what the i-sections of N(B) are for any set B< [k]^n in term of its i-sections, and then use induction to show that the i-sections of A are larger than that of its i-compression, and this gives the claim.
Now pick a B among all subsets of [k]^n of same size as A and smaller nbhd, which has minimal sum over elements in simplicial.
For n=2, we show that either B is an IS of simplicial or its nbhd is bigger than that of C.
For n>=3, tricky…
Use the vertex Isoperimetric inequality on the grid to prove the corollary that if A< [k]^n with
|A|>=|{x : |x|=|{x : |x|<=r+t}| for any t.
This is easy.
