Cosmas’ Generals, 4/21/2023 (2:45 PM -- 5:30 PM)

Examiners: 
Assaf Naor (chair) [AN]
Noga Alon [NA]
Jakub Witaszek [JW]

Special Topics:
Metric Embeddings
Extremal Combinatorics

ALGEBRA

[NA] State Cauchy's theorem for groups. How do you prove it?

[NA] Do you know how to prove the 1st Sylow theorem?

[NA] What do the other Sylow theorems say?

[JW] Suppose there are n people and m clubs, each club has an odd number of members and the intersection of any two clubs is even. Prove that the number of clubs m is at most n.

[AN] State and prove the Hilbert basis theorem.

[NA] State Hilbert's Nullstellensatz. 
For any ideal I in k[x_1, ... , x_n] over an algebraicly closed field k, if a polynomial g vanishes on the variety defined by I, then there exists natural number r such that g^r is in I. 
Is there any bound on the exponent r in terms of k and n, independent of g and I? 
Give a counterexample, where let's say we have a principal ideal in the univariate polynomial ring.

[JW] Prove the fundamental theorem of algebra using Galois theory.

REAL ANALYSIS

[AN] Construct a nowhere differentiable function.

[NA] What can you say about the points of differentiation of a monotone function on the reals? (it is almost everywhere differentiable) Prove it.

[AN] State the Hardy Littlewood maximal inequality.

[AN] What can you say about the differentiability of a Lipschitz function? (Rademacher's theorem) Prove it. Prove it when the domain of the function is R.

[AN] Talk about the Haar measure. What is the main theorem? (existence of Haar measure for compact groups with right invariant metric). Prove it.

[NA] You know that the Harmonic series diverges.
What about the series 1/(n log n)?
What about the series 1/(n log n loglog n)?
What about the series 1/(n log n loglog n logloglog n ... loglog...log n (log*n many times) )
where log*n is the iterated logarithm function, 
i.e. the number of times the logarithm function must be applied before the result is <=1.

COMPLEX ANALYSIS

[NA] State and prove Cauchy's integral formula.

[NA] Prove the fundamental theorem of algebra using complex analysis.

METRIC EMBEDDINGS

[AN] State and prove Assouad's embedding theorem.

[AN] Talk about padded decompositions and how you can construct one for planar graphs.

EXTREMAL COMBINATORICS

[NA] What is Hall's Marriage theorem? How do you prove it?

[NA] State Szemeredi's regularity lemma? Do you know the proof?

[NA] Can you use the regularity lemma to prove the triangle removal lemma?
Can the dependence of delta (triangle density) on epsilon (edge density to be removed) in the triangle removal lemma be polynomial in terms of 1/epsilon?

[AN] Give us your favorite construction for graphs of large girth. (I give Margulis' construction via free group in SL_2(Z) and reduction mod primes) What is the lower bound on the girth?

[NA] Can you give us an upper bound for the girth of the graphs in your construction?