An American Math Student at Cambridge

9 February 2009

Massive Update

Filed under: Uncategorized — Benson Joeris @ 10:32

I promise I haven’t died. Lots has been going on in Cambridge. We had around 6cm of snow last week – a big snow storm by English standards. I went sledding on the roof of the CMS. The roof has grass and is one of the only hills in Cambridge. There is a picture of the building at www.maths.cam.ac.uk. Cambridge, and especially Trinity were absolutely beautiful in the snow. Unfortunately the “make all my pictures really blurry” switch on my camera seemed to be turned on, so these were all I got:

There was a second snow storm last Friday that didn’t really do much but make enormous piles of slush everywhere and flood the Cam.

I was also racing on Friday in the Robinson Head. Despite the freezing, snowy conditions we did quite well. I’m in the 4th men’s boat for Trinity (“M4″) and we beat all the M4 crews, all the M3 crews except Trinity M3, and about 2/3 of the M2 crews. And we did it with  a completely new crew who had rowed together exactly once before the race.

This Saturday we have a regatta (side-by-side racing). and then, starting on the 24th is Lent Bumps! That’s THE race of the term: 4 days of ramming VIIIs together. Check out here if your curious. Our Bumps prospects look very favorable: in the Robinson head last Friday we beat the crews starting ahead of us by around 20 seconds. If all goes well we should be bumping the St. John’s (i.e. the big rival) M3, which would make our M4 higher than every M3 except our own.

In other news I think I’ve completed my first original, potentially slightly interesting mathematical result since arriving in Cambridge. Here is the necessary definitions and the theorem (the proof is somewhat longer):

A r-regular hypergraph H consists of a vertex set V(H) and an edge set E(H) where each edge is a set of r vertices from V(H). A hereditary property {\cal P} is an (infinite) set of r-regular hypergraphs that is closed under isomorphism and taking induced subgraphs (i.e. if H is in {\cal P} then any relabeling of the vertices of H is also in {\cal P}, and so is any hypergraph obtained by removing some vertices in V(H)). If {\cal P} is a hereditary property, then {\cal P}_n is the set of all H in {\cal P} such that H has n vertices (i.e. |V(H)|=n).

Theorem: The asymptotic behavior of |{\cal P}_n| (i.e. the number of hypergraphs in {\cal P} with n vertices) must fall into one of the following categories:

  • Constant: there is some c such that |{\cal P}_n|<c for all n
  • Polynomial: there are some integer polynomials p_1,p_2 such that p_1(n)\leq |{\cal P}_n|\leq p_2(n) for all n
  • Exponential: there are exponential function e_1,e_2 such that e_1(n)\leq |{\cal P}_n|\leq e_2(n) for all n
  • Factorial or above: there is some c such that n^{cn} \leq |{\cal P}_n| for sufficiently large n

So, for example, there is no hereditary property {\cal P} with |{\cal P}_n|=\log n as that would have to lie between constant and polynomial. This is a generalization of a result in a paper I was reading for my essay [Scheinerman and Zito, On the size of hereditary classes of graphs, J. Combin. Theory Ser. B, 61, (1994) 16-29]. They proved the graph case, i.e. where r=2.

Yay for wordpress \LaTeX!

1 Comment »

  1. Love the Photos, I only managed to take these: http://misplacedswag.wordpress.com/2009/02/02/we-wont-get-much-sleep/ and they are rather college-centric.
    Enjoyed reading your blog: interesting to see someone else’s perspective on coming to the uni (especially all the rowing!). Unfortunately, being only a first year mathmo, the maths is out of my league! Hope you’re enjoying part III, though.

    Comment by Robber — 11 February 2009 @ 18:13

    Reply

RSS feed for comments on this post. TrackBack URI

Leave a comment

Blog at WordPress.com.