Number Due Problems
1Thursday 2/7
  1. Prove Theorem 2.8 when H is the graph C4. (Note that this includes finding the expected value.)
  2. Consider the following variant on the construction of a graph whose triangle density is 1/8. Instead of working with four blocks of vertices, we have two blocks, V0 and V1. G0 will be the bipartite graph where all edges between V0 and V1 are present and no edges within these sets. G1 will be the "dual bipartite" graph where all edges inside the sets V0 or V1 are present, but no edges between the two. Gp will be the graph where, for each edge, we flip a coin which comes up heads with probability p and look at G1 (if the coin is heads) or G0 (if the coin is tails) to decide whether the edge belongs to Gp. What happens?
    Specifically:
    1. Find the expected values of the edge and triangle density of Gp.
    2. Prove, carefully, that (with high probability) Gp has close to the expected number of edges and triangles.
    3. Is there a value of p so that, with high probability, Gp has close to the same number of edges and triangles as R1/2?
    4. Explain why we used the more complicated example from class with four blocks of vertices rather than this simplified version.
2Thursday 2/21
  1. Prove that for every ε>0 there is a δ>0 such that if G is δ-regular and tK2(G)=p then |tV(G)-p2|<ε.
  2. Consider a bijection f:ℕ→(ℚ∩[0,1]) and the sequence <f(n)>. Prove that for every real number r in [0,1], there is a subsequence converging to r.
  3. Prove that for any finite graph H, there is an induced copy of H in [Gn]𝒰 if and only if {n | there is an induced copy of H in Gn}∈ 𝒰.
  4. Prove, carefully, that if Gn is the path of length n, that the ultraproduct is the union of uncountably many two-sided infinite paths and two one-sided infinite paths.
3Thursday 3/14
  1. Give an example of an internal set in an ultraproduct which is not definable (using the predicate symbols E for the edge and =). (You don't need a fully rigorous proof that the set is not definable.)
  2. There is a classic theorem of graph theory: a graph is bipartite if and only if it contains no cycles of odd length.
    1. Using an ultraproduct, demonstrate that no sentence of first order logic is equivalent to "has no cycles of odd length".
    2. Demonstrate (if you didn't in the first part) that an ultraproduct of bipartite graphs is always bipartite, but an ultraproduct of non-bipartite graphs might also be bipartite. Relate this to the fact that "has no cycles of odd length" is almost a sentence: it has the form "for every n, ..." where ... is a sentence (depending on n) saying there is no cycle of length 2n+1.
    3. What additional property does an ultraproduct of bipartite graphs have that a bipartite ultraproduct of non-bipartite graphs does not?
  3. Suppose G is an ultraproduct (with infinitely many vertices). Show that if G has infinitely many connected components then G has uncountably many connected components.
  4. Give an example of internal sets Ai and two different sets of representatives illustrating that A* (that is, [∪i≤nAin]𝒰) depends on the choice of representatives.
  5. Give an example of internal sets Ai and two different sets of representatives so that [Ann]𝒰 is empty with one choice of representatives, and all of V with the other.
4Thursday 4/4
  1. Write ℤn for the group of integers mod n. Consider the ultraproduct of these, [ℤn]𝒰: that is, the elements are sequences [an]𝒰 with each an∈[0,n-1]. This is automatically a group (define [an]𝒰+[bn]𝒰=[an+bn mod n]𝒰) with an ordering (define [an]𝒰<[bn]𝒰 if and only if {n|an<bn}∈𝒰). Consider the subgroup of "small" elements S⊂[ℤn]𝒰 where [an]𝒰∈S if, for every ε>0, either {n | an<εn}∈𝒰 or {n | an>(1-ε)n}∈𝒰. (The bifurcated definition is due to the "wrap around"; the point is that we want elements which are "within ε of 0".)
    1. Show that S is indeed a subgroup.
    2. Show that [ℤn]𝒰/S is isomorphic to the unit interval [0,1) with addition mod 1.
    3. Show that S is not internal, but is measurable (with respect to the Loeb measure) and has measure 0.
    4. The Loeb measure naturally gives a measure on the quotient group [ℤn]𝒰/S (as the measure of the coset). Show that the Loeb measure assigns, to each interval in [0,1), the same measure as the usual Lebegue measure. (It follows that the Loeb measure on the interval extends the Lebesgue measure. It is more difficult to prove the converse - that the Loeb measure is exactly Lebesgue measure.)
  2. Suppose G is a measurable graph maximizing the value of (tK3(G))2+tK4(G)-tK2(G). Find functions f and g so that, for almost every x, f(tK2(G,x), tK3(G,x), tK4(G,x))=g(tK2(G), tK3(G), tK4(G)). (The choice of function G is maximizing is chosen arbitrarily to illustrate the general method.)
5Thursday 4/18
  1. Consider the K4 "seminorm" ||f||K46=∫f(x,y)f(x,y')f(x',y)f(x',y')f(x,x')f(y,y') dμ4. Show that this is not a seminorm.
  2. Give an example of a set E in ℬ2,1 which is not a grid: that is, E is not a finite union of rectangles.
  3. Prove Theorem 5.16: If G is evenly distributed then whenever H=(W,F) contains no cycles, tH(G)=p|F|.
  4. Consider the induced graph removal lemma: if H=(W,F) is finite and tHind(E)=0 and ε>0, there is a B with μ(E△B)<ε so that THind(B)=∅. Attempt to prove this, and identify the step which makes this substantially more difficult to prove. (Do not expect to complete the proof, but do plan to make it over the first obstacle - how to make sense of tHind(f).)