Sasha Ovetsky Fradkin’s Generals – May 2007

Subjects:  Topics in Discrete Math (namely Matroid Theory and Combinatorial
Optimization), Algebraic Number Theory
Committee:  Paul Seymour (chair), Ramin Takloo-Bighash, Natasa Pavlovic


Matroid Theory (Seymour): 

- What is the matroid intersection theorem?  Prove the easy direction.
- What happens with three matroids?  
Me: In general?
Well just give some necessary conditions.
Me:  The analog of the two matroids case.
Ok, is this sufficient?
Me:  No? (that was the correct answer)
- Lets do some forbidden minors theorems.  What do you need to forbid for a
matroid to be graphic?  Do you know list for ternary? (yes) 
- What is a regular matroid?  What is the relationship to unimodular matrices?
Which minors do you need to forbid in this case?
- If you have a representation for a matroid over some field, how would you get
the representation for the dual?  (I should have known this right away but
somehow it took me a really long time + hints)
- Lets talk about graphic matroids.  If two graphs have the same matroid how 
are they related?  (I knew what happens if the graphs are three connected or 
not two connected but I forgot what happens in the two connected case)

Combinatorial Optimization (Seymour):

- State Lucchesi-Younger.  Outline proof.
- What is the matching polytope?  State Edmond’s theorem.
- Why is the third (cut) condition necessary?  Give an example (gave triangle
with 1/2 weighing on all the edges).
- What if the graph is bipartite? (then you don’t need the cut condition!)  
- Why? (because it is automatically satisfied)
- What is the multicommodity flow problem?
- We had a theorem in class that said that if the graph + added demand edges is
planar then one can solve multicommodity flow problem.  How was this related to
T-cuts?  (I remembered seeing this in my notes but didn’t remember what it said) 
When is it true that nu=tau for T-cuts?  (I totally knew this but somehow didn’t
realize what was being asked until he told me the answer).

Algebra + Algebraic Number Theory (Takloo-Bighash):

- Talk about Galois theory.
- Compute the Galois group of x^3-2.  
- Discussion of cyclotomic polynomials (don’t really remember the details here
other than the fact that I was being very stupid at this point)
- Consider the minimal polynomial for a primitive mth root of unity.  Prove the
following: if p divides this polynomial evaluated at some integer a and (p,m)=1
then m divides p-1 (Here there was a lot of mumbling and writing random stuff on
the board..)
- Ok, how would you use the above fact to show that there are infinitely
many primes congruent to 1 mod m (this should have been very easy but at this
point I wasn’t thinking at all so it still took a hint).
- So this is a special case of Dirichlet’s theorem on primes in arithmetic
progressions which is a special case of Cebotarev Density (he meant to ask this
as a question but ended up saying the answer instead).
- State Cebotarev Density Theorem (finally something I could just blurt out from
memory).  
- Derive Dirichlet’s theorem from it.  
- Last question: give a number field with class # not equal to one (I said 
Q[sqrt(-5)] and he didn’t even ask me to justify it).

Complex and Real Analysis (Pavlovic)

- What is Goursat’s theorem?  How does one prove it? (semi-detailed outline)
- What is the use of this theorem? (can use it to prove Cauchy’s theorem)
- And what is Cauchy’s theorem used for?
- What is Louiville’s theorem?  Prove it.
- What are the Cauchy integral formulas?
- How would you use Louiville to prove the fundamental theorem of algebra? (she
actually said fundamental theorem of calculus first but I
didn’t even notice until she corrected herself)
- Are the upper half plane and disc conformally equivalent?  Write down
the map and it’s inverse.
- What is the map for mapping the upper half plane to a horizontal strip?  (I knew
this should be easy but somehow blanked and got it only after a hint)
- And these are special cases of what theorem?  What does it say?
- Show that e^(-pi*x^2) is it’s own Fourier transform using contour integration.
- What are some properties of the Fourier transform?  More properties?
- Monotone convergence theorem, Fatou + proof from Monotone convergence, dominated
convergence theorem + outline of proof from Fatou.

General comments: The exam was 2.5 hours.  There were many awkward pauses (mostly
during the first two sections) but the examiners were generous with hints.  Remember
that you don’t have to answer every question to pass so don’t panic when you don’t
know something.  There will most likely be questions that you will not have studied
or expected but that is all part of the goal and the experience.  It’s important to
talk to the examiners before the exam and find out what they expect you to know.  I
also suggest getting plenty of sleep and rest the week of the exam.