Melody Chan's generals
Committee: Paul Seymour (chair), Samuel Grushevsky, Elon Lindenstrauss
Special topics: Graph theory and combinatorial optimization; Additive number theory
Date: May 25 2007, 10AM - 12:40PM

ANALYSIS:
(EL) state lebesgue density theorem.  (hmm, i know the differentiation theorem)  well ok, state that.
so what would it mean when applied to a characteristic function? 
what's the maximum modulus principle?  now suppose we have a holomorphic function defined on the strip
0 <= Re(s) <=1 and its modulus is bounded on the lines Re(s) = 0 and Re(s) = 1, does it follow that
it's bounded on the whole strip?   [plus more questions along these lines, i think]
(SG) can you think of a conformal map from a strip of width 1 to a strip of width 2?  ok, what about
a 1x1 box to a 1x2 box?  what do you know about what would happen to the boundary?  [there were several
more questions that i couldn't really answer about whether particular boundary maps could be realized
for various mappings.]
(EL) what's a hilbert space? what's a compact linear operator? (don't know... i know what a bounded
linear operator is...) well okay, tell me what that is. example? less trivial example?  is it possible
to find one without an eigenvector?  [i got that it couldn't be finite dimensional, but severely
blanked on the follow-up questions, and spent a long time just trying to dig myself out] 
(EL) setting is functions from say [0,1] to R.  what's uniform continuity? prove that the uniform limit
of a sequence of continuous functions is continuous.  if a sequence of differentiable functions
converges uniformly to a differentiable function, does the sequence of derivatives converge to the
derivative of the limit? (um...yes?) actually no, so give us a counterexample.  ok, now what about in
the complex case? [stated the theorem] prove that.   

ALGEBRA
(SG) suppose i asked you to classify groups of order 4.  (Z_4 and Z_2 x Z_2).  why isn't there anything
else?  ok, now which of those could be realized as a galois group over Q? [In working this out, i
temporarily forgot that the multiplicative groups of finite fields are cyclic!  so i had to prove it
and then finish answering the question]  
do you know any representation theory?  what about representations of A_4--give a nontrivial one.
(symmetries of a tetrahedron) ok, so what else is there--how many irreducible reps do we have? so what
are their degrees etc... [walked through character table of A_4] 
can we solve general quadratic equations by radicals? and what about cubic... (i said yes, yes, yes,
and no, because of solvability of S_n) let's talk about that, so define solvable group.  (EL) example
of a solvable nonabelian group. (dihedral) what is that--write it out, why is the subgroup of
rotations normal?  ok, why are index 2 subgroups normal?  
(SG) show A_4 solvable.  by the way, what are the sylow theorems?  so do they tell you anything about
whether this index 3 subgroup of A_4 is normal? [no, but it is anyways]
possibly some other questions which i don't remember, but nothing non-standard.

ADDITIVE NUMBER THEORY
(EL) state freiman's theorem.  [i mentioned which specific bounds i could prove vs. what was best
known, but he was not interested].  what kind of groups does your statement apply to? (oh, torsion
free) would it be harder to prove for, say, Z^2 than for Z? [no--he was happy with my general
indication that one can just use a freiman isomorphism to get down to Z].  what about if our ambient
group is something like (Z_2)^n instead?  (then the theorem is even easier) state it.  prove it.
(just had to state plunnecke-ruzsa inequalities in the process, without proof).
Balog Szemeredi Gowers theorem.  An example of how we would use this?  (i offered exponential sum
estimates in F_p: this refers to a specific paper of Bourgain et al.)  ok state this result.  where
do we use BSG in the proof--i don't see a graph anywhere?  what do you know about the fourier
transform of elements in F-F for the refinement F that you get?  [i sat on this for a while, unsure,
then:] well, the point is, we don't know much about them at all.
ok, so what other tools do we use? (sum-product estimate over F_p).  state that result.  proof?
(spent several minutes giving generally a very high level outline of the proof.  mine differed in
several respects from what he had in mind, so i was asked to give details only in those areas).
ok, i think i'm satisfied.

GRAPH THEORY & COMBINATORIAL OPTIMIZATION
[graph theory was from R. Diestel's book; combinatorial optimization was from class notes.]
(PS) let's start with basics.  koenig's theorem.  [stated it].  (EL) wait! i want to learn some graph
theory! [so PS periodically made me stop and define things.]  
(PS) now is this true for general graphs? (no e.g. odd cycle) ok, well what is true in general?
[didn't know the theorem he had in mind] well what about the existence of a perfect matching? [stated
tutte's theorem on that] so now what if we wanted, say, just a k-edge matching? [i couldn't derive
what he wanted on the spot, so was advised to learn it: it's a theorem of tutte & berge].
kuratowski's theorem.  proof? [it had been a while since i had read this and stood there trying to
recall it...] well, if you don't know it now, you aren't going to be able to reconstruct it.
what do you know about choosability?  [defined it, started listing things i knew] what about galvin's
theorem? proof? [for the proof, he was satisfied with "you use kernels, and the stable marriage
theorem"].  
Nowhere zero flows.  why don't you explain what they are, and give some theorems. [defined them,
started listing theorems...] what about region coloring? (oh yeah, so a planar graph is
p-region-colorable iff it admits a n.z. p-flow) can you prove that a planar cubic graph is 4-region
colorable iff it is 3-edge colorable? ok, what about edge-connectivity--can you prove that a
4-edge-connected graph admits a n.z. 4-flow?  [when i didn't answer immediately] you said you can prove
the 8-flow theorem--well, that's my hint. (oh yeah, so first we can find 2 edge-disjoint spanning
trees...) how do you know that? [nash williams tree-packing theorem.  then he wasn't interested in the
end of my proof]
what's a well-quasi-ordering?  what's the statement for finite trees?  ok, prove it.  wait, before you
say anything about trees, you need a lemma. (if A is WQO'ed then finite subsets of A are too).
combinatorial optimization:
state edmond's matching polytope theorem.  how is this related to whether a graph is k-edge-colorable?
[i didn't fully answer this question in the end--i could see that the uniform 1/k weighting being in
the matching polytope was necessary, but not sufficient e.g. petersen graph--and couldn't plug the gap].
well, ok, let's move on.
state lucchesi younger theorem.  define nu, tau, etc. for the audience.  proof outline.
perfect graphs: define.  prove that G is perfect iff its complement is.  examples. (comparability graph
of poset) prove it is perfect. [started using dilworth's theorem, for the complement] no, the other way
is easier.  ok, more examples. [after a misstatement, we got to line graphs of bipartite graphs]. ok,
so what theorem would that translate to? (i said some theorem of koenig's, for sure.  i started trying
to think of what it would be, but after about 10 seconds he decided to drop it) well, ok, it's one of
koenig's theorems.  

~~~~~~~~~
good luck!!!