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!!!