29 March 2007, evening time
Krishna asked me, “if G has a girth of at least 6 and contains a vertex of degree at most 2 then G is 3 colourable.” It took me a couple seconds to remember what that all meant, and then a little longer to figure out how to go from there. Its kind of sad though that I am happy about being able to do a 2nd year Graph Theory problem — an easy one at that. Sometimes I feel like I used to be smart and I’m getting progressively dumber. My 4th year Graph Theory notes are mental. Well, to be fair, I’m quite sure I thought they were mental at the time as well.
[1] Mathematics
23 June 2004, the wee hours
I attended a talk today by Henrik Lenstra on Escher and the Droste Effect. The talk examines the mathematics behind M.C. Escher’s print of a man viewing a painting in a gallery that turns in to the gallery itself. Escher left the middle of this print blank, thought it apparently need not be. The talk was quite interesting, and the art produced from the research is really quite amazing to see.
I was already aware of Lenstra from his work in cryptography. Lenstra seems to have been involved in number theory for quite some time. His name comes up when discussions turn to factoring integers, in particular the Number Field Sieve. The Number Field Sieve is the fastest algorithm to factor integers. It is based on another factoring method called Random Squares.
I think the notation used to talk about running times of algorithms similar to the Number Field Sieve was developed by Lenstra, though I could be mistaken on this. The running time for an algorithm is the number of primitive operations needed to solve an input problem of a given size. The running time for algorithms based on the Random Square method generally have the form e(c + o(1))(ln n)α(ln ln n)1-α, where α and c are constants, and n is the size of the input. This is usually abbreviated to Ln[α,c]. The running time of the Number Field Sieve is Ln[1/3,1.98], which is a sub-exponential algorithm.
[7] Mathematics | Life
