Friday, March 27, 2009

What's in a number?

March 28, 2009 2:00 am

What's in a number?

I’ve recently been thinking a lot about the numbers that we use in music performance/composition/analysis. My students seem to be confusing several things and their confusion got me to thinking about how to disentangle some of these ideas. I welcome any comments or suggestions on how to understand these things.

1. Figured bass. Figured bass uses Arabic numerals (1, 2, 3, etc.) under (or sometimes over) a given bass note to indicate which diatonic (that is, in the key) intervals are to be played above (i.e., in the right hand) that bass note. Any note you add above a bass is unaltered unless there are accidentals in the figured bass.

Many students try to reverse-engineer the figured bass symbols by trying to figure out the chord/Roman numeral first. This is a bad idea because figured bass symbols alone tell us nothing about chords or harmony. Once you add the notes above the given bass note, then try to figure out the harmony/Roman numeral. The example below highlights this. The A in the bass has a figure 6 underneath it. In the key of F major, this produces a first-inversion tonic harmony. In the key of G major, it produces a first-inversion diminished vii chord. In the key of D major, it produces a first-inversion minor iii chord. In the key of C major, it produces a major subdominant chord.

I often tell my students that figured bass evolved as a shorthand notation for species counterpoint. That is, figured bass actually suggests lines, not chords. Consider the example below:

If you look at those examples without worrying about vertical sonorities, the figured bass makes quite a lot of sense. Once you begin trying to assign Roman numerals, the task becomes a bit muddier. In the first example, we can easily understand the E-F motion in the soprano as some kind of neighbor motion or perhaps as the beginning of a passing motion. I prefer that interpretation to one which says the first chord is a root-position tonic and the second chord is a first-inversion submediant. In the second example, we see a collection of upper neighbors above a pedal bass. Sure, the notes on beat two add up to a iv chord, but is it really a chord or just a collection of neighbor notes? In the last two examples, we see suspensions notated in figured bass, complete with accidentals that tell us to raise the leading tone.

In short: figured bass tells us diatonic intervals above the bass and nothing else. If notes are to be altered, the accidentals will appear in the figured bass. Figured bass is simply a shorthand for linear motion.

2. Roman numerals. Roman numerals tell us quite a lot about a particular harmony. They tell us how the chord functions in a particular key. They can tell us quality (major chords typically get upper-case Roman numerals; minor and diminished chords typically get lower-case Roman numerals). They tell us the scale degree that forms the root of that particular chord.

Many harmony textbooks seem to favor a micro-managed approach to Roman numerals: every vertical sonority should probably have a Roman numeral. If you can’t determine the Roman numeral for a given slice of music, then there’s probably a non-harmonic tone stuck in there somewhere. I personally prefer a broader view, more in line with Schenker’s concept of Stufen, where a Roman numeral is used to indicate the prevailing harmony of a passage. Other intermediate harmonies are accounted for in terms of passing chords, neighboring chords, etc. Such an approach draws attention to the prevailing linear organization of most music.

3. Inversion symbols. Inversion symbols are Arabic numerals affixed to Roman numerals that tell us which element of the chord is in the bass. They have a lot in common with figured bass symbols, but I think they differ in significant ways. The cadential 6-4 chord is perhaps the most glaring example of the confusion that can arise when these symbols try to play nice together. Consider the example below, which includes several different ways of indicating a cadential 6-4.

The first example suggests that the C and the E of the first chord are suspensions over a dominant harmony. The C and the E have pushed the chord tones out of the way and are creating a lovely dissonance over the bass. This example shows the linear nature of the cadential 6-4. The second example labels the first chord as a tonic-functioning harmony that just happens to have the fifth of the chord in the bass. We were probably taught somewhere along the way that this chord is consequently unstable because the fifth is in the bass. Here, the Arabic numerals attached to the chord say nothing of the linear behavior of the upper voices. The third example is a kind of fusion of the first two: it labels the individual chords as such, but the bracket underneath suggests that both chords are in the service of an overall dominant harmony. (I don’t much care for this approach, since it looks too much like a secondary dominant.) The final approach again suggests two discrete entities, but highlights the instability and structural weakness of the first chord by not assigning it a Roman numeral.

A related example (and the one which sparked this whole train of thought) comes from a common cadential figure in Bach chorales:

(From chorale no. 9, “Ermuntre dich, mein schwacher Geist”)

Here, the Arabic numerals are purely figured bass: they can’t be confused with a chord inversion like the cadential 6-4 examples above. I think this is where my students’ (and, to some extent, my) confusion began. Is there a way we can disentangle these closely related symbols without reinventing the wheel? Any thoughts?

UPDATE: We started talking about modal borrowing (a.k.a. modal mixture) today and this brought up another instance of number confusion: the bVI and bIII chords. When you borrow a mediant or submediant chord from the parallel minor and bring it into major, the root of the chord is lowered. I advise my students to interpret the Roman numeral as “in the major key, lower scale degree 3 and build a major triad on that root.” The flat before the Roman numeral is an operation that applies to the root of that chord.

From the Top

March 28, 2009 2:00 am

From the Top

Last night, Texas Tech hosted a live taping of the radio program From the Top. The program features talented young classical musicians in performance, and includes interviews with the students in an effort to show that many classical musicians don’t fit the stuffy stereotypes.

This rather informal format–musical performances interspersed with interviews, dialogue, and humor–seems to me an interesting approach to not only radio programming, but concertizing in general. Who wouldn’t want to see a chamber music concert where the members of a string quartet (for instance) talked about why they chose the piece, why they chose to study music, etc. I’m not suggesting that all concerts should be this way, but it might be a good way to bring in the skeptics. One girl last night, a cellist, spoke about her love of snowboarding which has so far resulted in a broken arm and a broken leg. She delivered quite a performance of the first movement of Shostakovich’s first cello concerto (limbs intact), not a stuffy piece by any means. One of the other performers played some classical guitar pieces by Barrios, then proceeded to wow us with his flamenco skills, and a Jimi Hendrix cover. He was nine years old.

Also of interest was the type of music that these students played. The concert featured five performers playing Prokofiev, Shostakovich, Lutoslawski (!), Barrios, and another composer whose name escapes me at the moment (it sounded very much like one of the Paris Conservatory test pieces for flute, probably from the 1920s). All of this music is pretty serious 20th-century music, which I didn’t think most people–let alone (most) teenagers–would be interested in.

It seems like this year in particular, we have quite a lot happening musically in Lubbock, a town which usually gets passed over by big names. We’ve had Mark O’Connor recently, and Mark-Andre Hamelin (an alumnus of my alma mater, Temple University) will be here in October.

The program will air sometime in mid-December. Tune in and you might just hear members of the TTU Theory faculty applauding.

Partwriting help V

March 28, 2009 2:00 am

Partwriting help V

Today I’ll write a bit about secondary dominant chords, which are also called applied chords in some textbooks. Secondary dominants temporarily make the chord that comes after them sound like a tonic, albeit briefly. We call this phenomenon tonicization. Very often, you’ll see secondary dominants at cadence points as a method of intensifying the forward motion to the cadence.

Any major or minor diatonic triad can be preceded by its secondary dominant. Diminished triads (viio in major and iio in minor) cannot be tonicized because they cannot serve as the tonic chord in any key.

Secondary dominant chords come in several shapes and sizes. Most commonly, perhaps, is the secondary dominant seventh chord. One can have a secondary dominant triad, but if the purpose of the chord is to intensify the motion to the next chord, the chordal seventh in conjunction with the leading tone really drives the progression forward. Secondary dominants also include chords built on the leading tone, like viio, viio7, and their half-diminished brethren. When I say secondary dominants, I’m using “dominant” in the broader sense–that is, I’m referring to dominant-function chords.

One of the most commonly encountered secondary dominant chords is the dominant of the dominant. To determine what this look like, let’s first find the dominant of C major, which is G. The dominant of the dominant will have a root that is five diatonic steps above the root of the dominant: in this case, the root of the dominant of the dominant is D. We also need to find the leading tone that will propel us to the dominant chord. In this case, the leading tone to G is F#. Notice that F# is not in the key of C major. We’ll need to be sure to add this accidental in our exercises. To round out the chord, we need to construct a major-minor (dominant) seventh chord using D as the root and F# as the third. An A and a C complete the chord. We would label this chord V7/V, indicating that it is the dominant seventh of the dominant.

The same resolution tendencies apply to secondary dominants that apply to ordinary dominants. The chordal seventh must resolve down; the leading tone must move up by step to the “tonic,” unless it’s in an inner voice in which case it can leap down to the fifth of the following chord. It may help you to think about resolution in terms of complete/incomplete chords: usually, either the V chord or the I chord must be incomplete in order to avoid parallels and obey the resolution tendencies.

As I said earlier, any triad can be preceded by its secondary dominant. We can find V/iii chords, or V7/IV chords using the same method detailed above. The chords would then be labeled accordingly.

A few helpful pointers:

  • Secondary dominants will almost always require at least one accidental, usually applied to the leading tone.
  • Secondary dominants may resolve deceptively. I’m not going to get into that in this post for various reasons. Consult your local theory textbook for more information.
  • The vast majority of pedagogical approaches do not allow for things like ii/III or VI/VI. If your “numerator” (the Roman numeral above the line) is not V, V7, viio, or viio7, it’s most likely incorrect.
  • When writing a V/IV (in major or minor) be sure always to use a V7 chord. The dominant of the subdominant is equivalent to the tonic chord. The added seventh will distinguish the chord from a plain vanilla tonic triad.
  • You might wish to think of secondary dominants as substitutes for their diatonic partners. A V7/V chord will stand in for a ii chord, and it actually looks quite a lot like it: D F# A C vs. D F A in C major. A V7/IV chord looks like a I chord; a V7/vi looks like a iii, etc.

If I have time, I’ll add some score examples later. Stay tuned!

Theory calisthenics

March 28, 2009 2:00 am

Theory calisthenics

On Friday, one of my colleagues happened to mention a composer who got up every morning and harmonized a chorale, much like someone doing a crossword puzzle with their morning coffee. Every day he picked a different style in which to harmonize it. One day might be Bach; another, Schoenberg.

Over the weekend, I graded a particularly bad crop of homework assignments. I have a class of sophomores and we were in the midst of talking about secondary dominants. The assignment asked them to harmonize “Jesu, meine Freude.” Not only were the secondary dominants used in very strange ways, but there were tonicized diminished chords, ii-i progressions at cadences, doubled leading tones all over the place, and the like.

I can’t take every other class period to re-teach the rules of part writing to my students. But it seems to me that if we borrowed this composer’s idea, that might be a good way to help the students practice their part writing.

So next week we’re going to start theory morning calisthenics. At 8:00, we’re going to meet at the coffee shop on campus–faculty, graduate students, undergraduate students, etc.–and we’re just going to work for 45 minutes on harmonizing a chorale for the day. No pressure, no grade–just something to get the theory juices flowing first thing in the morning. My plan is that everyone gets the same chorale and can work on as much as they are able using whatever vocabulary is available to them. I might suggest the graduate students and composition majors harmonize in the style of _____. Then we can compare notes (pardon the pun) after about 45 minutes and see who did what. I’m hoping that the less experienced will take advantage of the more experienced and look over our shoulders, ask for help, etc.

We’re going to pilot this for two weeks, meeting Monday and Wednesday mornings (I doubt anyone–myself included–wants to get up early on Friday and do theory). We might add Tuesday-Thursday if it looks like there’s a demand. I think I’ll advertise it on Facebook, too, so that it looks cooler than it really is.

Our trumpet professor does 7:00am (I think) trumpet warm-ups every morning and they’ve been pretty successful, as far as I can tell. Hopefully the theory calisthenics will be equally as helpful.

Meta-post

March 28, 2009 2:00 am

Meta-post

I just finished adding tags to many of the older posts here on TTU Theory. I don’t know that it’s something I could have done at the genesis of the blog (at the very least, I don’t think that Blogger offered that capability). But now, I get to survey the 130 posts that I’ve written and see how they organize themselves. I ended up with about 14 categories of posts:

American Idol
Famous People
Humor
iPod
Listening

etc.

It occurs to me that in organizing my posts, I just created a sort of theory in much the same way music theorists do. I surveyed a body of work (in this case, my collected blog posts), observed patterns in that body of work, and then tried to group those patterns under some kind of common heading. Some posts don’t fit neatly into any of my categories: let’s call them non-harmonic posts, or maybe non-functional posts, or maybe passing posts.

If you’re interested in reading everything I’ve written about iPods, you can click on the “iPod” heading and all of the related posts will be retrieved.

Now, I could have come up with 130 category labels for my 130 posts, but that wouldn’t be terribly useful, would it? And there are some posts that really don’t fit neatly into one category, but can be understood as somehow belonging to two (or more!) categories. These are a bit like pivot chords.

Look for some partwriting help later this week…

Free Online Video Lectures

March 28, 2009 2:00 am

Free Online Video Lectures

From my bookmarks : here are some great websites with video lectures :

  • Research Channel : Awesome site with lots of theory talks. Most of the theory talks are either from University of Washington (or) Microsoft Research. I used it extensively during my first year of PhD.
  • Last but not the least, Academic Earth covers many areas with good quality video lectures.

Did I miss any good sites ? Please leave a comment if you know other websites with free video lectures.

Dick Lipton's and Noam Nisan's Blogs

March 28, 2009 2:00 am

Dick Lipton's and Noam Nisan's Blogs

There are two new theory blogs…..

  • Dick Lipton’s Gödel's Lost Letter and P=NP : This is an awesome blog. During my first semester at GeorgiaTech I took Dick’s course on ‘Open Problems in CS theory’. What an excellent course that was !! In every class, Dick proposed at least three open problems along with possible ways to attack them and required references. Since, it was my first semester at Gatech, some of these problems intimidated me. Nevertheless, I maintained a special notebook and scribbled each and every problem and references he mentioned, hoping to revisit them later. I am gald that all his open problems are being documented in his blog.

Complexity of Ken Ken Game

March 28, 2009 2:00 am

Complexity of Ken Ken Game

I came across this puzzle named Ken Ken. It is Sudoku-type puzzle with arithmetic constraints. Here is a complexity question :

  • Is solving n x n Ken Ken puzzle NP-complete ?

NP-completeness results are known for similar games like Sudoku. Here is a paper on mathematics of Septoku. Here is David Eppstein’s list of games with complexity results.

Sloan Fellows 2009

March 28, 2009 2:00 am

Sloan Fellows 2009

Sloan Research Fellows for the year 2009 are announced. The list can be found here. For a list of theory Sloan fellows (and related comments) follow this post on complexity blog.

2008 ACM Turing Award

March 28, 2009 2:00 am

2008 ACM Turing Award

ACM has named Barbara Liskov as the winner of the 2008 Turing Award…… “for contributions to practical and theoretical foundations of programming language and system design, especially related to data abstraction, fault tolerance, and distributed computing.”

Free Algebraic Curves Book

March 28, 2009 2:00 am

Free Algebraic Curves Book

William Fulton’s Algebraic Curves book is available free online. What distinguishes it from other books is the excellent set of exercise problems.

STOC 2009 accepted papers

March 28, 2009 2:00 am

STOC 2009 accepted papers

STOC 2009 accepted papers list is here.
Here is a list with the abstracts

Train Probability Puzzle

March 28, 2009 2:00 am

Train Probability Puzzle

The probability of observing a train in 30 minutes on a track is 665/729. What is the probability of observing a train in 5 minutes ?
Hint : Shoot for an elegant solution.

Linial-Nisan Conjecture

March 28, 2009 2:00 am

Linial-Nisan Conjecture

As most of you already know, Linial-Nisan Conjecture is settled by Mark Braverman. This settles a major open problem. Read the following blog posts for more details :

Braverman’s paper is on his homepage.

Pure Mathematics

March 28, 2009 2:00 am

Pure Mathematics

This comic strip from Abstruse Goose is simply aaawesome !! Click the image to enlarge.

Long Live Pure Mathematics…..

Finding a Second Hamilton Circuit

March 28, 2009 2:00 am

Finding a Second Hamilton Circuit

Given an undirected graph does it have a Hamilton circuit ? It is well-known that this is an NP-complete problem. Consider the following problem :

  • ANOTHER HAMILTON CIRCUIT : Given a Hamilton circuit in a graph find another hamilton circuit.

It is easy to see that ANOTHER HAMILTON CIRCUIT is FNP-complete. What if we are given a Hamilton graph which is guaranteed to have a second Hamilton circuit. Following is a simple exercise :

  • Exercise : Prove that if a cubic graph has a hamilton circuit then it must have a second one

The above exercise is called Smith’s Theorem. Now consider the following computational poblem :

  • SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit.

Since the second hamilton circuit is guaranteed to exist, SMITH belongs to complexity class TFNP. Note that TFNP is a semantic class. In a beautiful paper [1] Papadimitriou defined several syntactic classes (e.g., PPA, PPAD, PPP) in TFNP. Papadimitriou proved that SMITH is in the complexity class PPA [1]. Here is an open problem mentioned in [1].

  • Open Problem : Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.

[1] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994)

Troyis Game

March 28, 2009 2:00 am

Troyis Game

I came across this game called Troyis. Being a theoretician, whenever I come across a new game, the first question that comes to my mind is “What is its complexity ?”. Here is the decision version of Troyis :

  • TROYIS : Given an instance of Troyis, can you paint all the white cells in <= k clicks ?

Here is a puzzle : Prove (or disprove) that TROYIS is NP-complete.

Polynomials difference puzzle

March 28, 2009 2:00 am

Polynomials difference puzzle

Here is a cute puzzle about difference of polynomials.

Caterpillar graphs are graceful

March 28, 2009 2:00 am

Caterpillar graphs are graceful

Let T(V,E) be a tree, with |V|=n. A graceful labeling of T is an assignment of labels (from 1 to n) to the vertices such that if the edges are labeled with the absolute difference of their incident vertices, then each edge receives a unique label (i.e., each of the n-1 edges receive labels fron 1 to n-1). It is easy to see that stars and paths are graceful.

A caterpillar graph is a tree such that if all leaves and their incident edges are removed, the remainder of the graph forms a path. Here’s a cute problem :

  • Prove that all caterpillar graphs are graceful

Hint : Given a graceful labeling find another labeling with a special property and apply induction.

Have fun solving this. I almost gave you the solution.

Legendre's Conjecture

March 28, 2009 2:00 am

Legendre's Conjecture

Bertrand’s postulate states that for every positive integer n, there is always at least one prime p such that n < p < 2n This was proved by Chebyshev in 1850, Ramanujan in 1919 and Erdos in 1932.

Legendre’s conjecture states that there is a prime number between n2 and (n+1)2 for every positive integer n. It is one of the four Landau’s problems, considered as four basic problems about prime numbers. The other three problems are (i) Goldbach’s conjecture : can every even integer n > 2 be written as the sum of two primes ? (ii) Twin prime conjecture : are there infinitely many primes p such that p+2 is prime ? (iii) are there infinitely many primes p such that p-1 is a perfect square ? All these problems are open till date.

How about the following generalization of the Bertrand’s postulate :

  • Does there exist a prime number p, such that kn < p < (k+1)n for all integer n>1 and k <= n ?

A positive answer for k = n would prove Legendre’s conjecture.
I proved the following theorem :

  • Theorem : For any integer 1 < k < n, there exists a number N(k) such that for all n >= N(k), there is at least one prime between kn and (k+1)n.

My proof is based on Erdos’s proof of Bertrand-Chebyshev theorem and uses elementary combinatorial techniques without appealing to the prime number theorem. You can find a preprint on my homepage.

My Favorite Math Movies

March 28, 2009 2:00 am

My Favorite Math Movies

Here are my top five math movies, along with my favorite quotes. I will not talk about the storylines, because I don’t want to spoil the fun.

N is a number : I was sad that I did not see Paul Erdös in person, until I saw this documentary. This is a documentary about Paul Erdös, the wandering mathematician, the man who loved only numbers. Watch this if you want to see him walk, talk, crack math jokes and inspire people around him. You can also see other famous mathematicans collaborating with him.

  • Euler, when he died, he simply collapsed and said “I am finished”. An when I told this story, somebody callously remarked : “Another conjecture of Euler’s was proven”.
  • What is the purpose of life ? “Prove and conjecture and keep the SF’s score low”.

Pi : I should warn you that this is a disturbing move. Here are couple of quotes.

  • Restate my assumptions: One, Mathematics is the language of nature. Two, Everything around us can be represented and understood through numbers. Three: If you graph the numbers of any system, patterns emerge. Therefore, there are patterns everywhere in nature. Evidence: The cycling of disease epidemics;the wax and wane of caribou populations; sun spot cycles; the rise and fall of the Nile.
  • You want to find the number 216 in the world, you will be able to find it everywhere. 216 steps from a mere street corner to your front door. 216 seconds you spend riding on the elevator. When your mind becomes obsessed with anything, you will filter everything else out and find that thing everywhere.

Proof : This is a perfect math movie with top-notch performances from Gwyneth Paltrow and Anthony Hopkins, an awesome screenplay and a satisfying ending. The following conversation about Hardy-Ramanujan number is aptly placed in the movie.

Robert: Catherine, if every day you lost were a year, it would be a very interesting freaking number.
Catherine: 33 and a quarter years is not interesting.
Robert: Stop it, you know exactly what I mean.
Catherine: 1729 weeks.
Robert: 1729, great number. The smallest number expressed …
Robert and Catherine: … as the sum of two cubes in two different ways.
Robert: 123 + 13 = 1729.
Catherine: And 103 + 93. Yes, we’ve got it, thank you.
Robert: You see? Even your depression is mathematical.

A Beautiful Mind : Well, everybody knows about this oscar-winning movie.

  • Sometimes, our expectations are betrayed by the numbers.
  • Good morning, eager young minds.
  • Find a truly original idea. It is the only way I will ever distinguish myself. It is the only way I will ever matter.
  • [Sol] John, you should go easy. There are other things besides work. [Nash] : What are they ?

Good Will Hunting : In my previous post I mentioned an elementary graph theory problem from this movie. Also, there is a scene in which the characters talk about a math problem and joining two vertices of a tree. Are they talking about 1-trees ? If you don’t know what a 1-tree is, read Held-Karp relaxation of Traveling Saleman Problem. The best scenes of the movie are the conversations between Will and Sean.

  • You really hypnotised me, you know.
  • I’m pumped! Let the healing begin!
  • I can’t learn anything from you, I can’t read in some freaking book. Unless you want to talk about you, who you are.
  • [Will] You just cash in your chips and you walk away ? [Sean] Hey, at least I played a hand.

Btw, Pi, Proof and A Beautiful Mind have excellent soundtracks too. I would like to see more movies of this kind. If you know of any good math movies, leave a comment.

The Good Will Hunting Problem

March 28, 2009 2:00 am

The Good Will Hunting Problem

Here is a problem from the movie Good Will Hunting, shown in the screenshot below.



For the the graph G(V,E) shown above, find the following :

  • The adjacency matrix A :
  • The matrix giving the number of 3 step walks in G : [Ak]ij is the number of paths of length k from i to j. So, the answer is A3.
  • The generating function for walks from point i to j : The generating function is as follows. Here are more examples of generating functions.

  • The generating function for walks from points 1 to 3 : Simplify the above formula using cramer’s rule for i=1 and j=3.

How are mathematics texts written ?

March 28, 2009 2:00 am

How are mathematics texts written ?

If you are wondering how mathematics texts are written, check this out. Very funny ;)

Click the above picture to enlarge.

List Coloring

March 28, 2009 2:00 am

List Coloring

I have been reading some papers on list-coloring of planar graphs. Here’s a quick overview of this topic.

A proper coloring of a graph is an assignment of colors to vertices of a graph such that no two adjacent vertices receive the same color. A graph is k-colorable if it can be properly colored with k colors. For example, the famous Four Color Theorem states that “Evey planar graph is 4-colorable“. This is tight, since a complete graph on four vertices is 4-colorable but not 3-colorable. Deciding if a graph is 3-colorable is NP-hard. It is natural to ask which planar graphs are 3-colorable. Grotzsch’s Theorem states that “Every triangle-tree planar graph is 3-colorable“.

Given a graph and given a set L(v) of colors for each vertex v, a list coloring is a proper coloring such that every vertex v is assigned a color from the list L(v). A graph is k-list-colorable (or k-choosable) if it has a proper list coloring no matter how one assigns a list of k colors to each vertex.

If a graph is k-choosable then it is k-colorable (set each L(v) = {1,…k}). But the converse is not true. Following is a bipartite graph (2-colorable) that is not 2-choosable (corresponding lists are shown).


A graph is k-degenerate if each non-empty subgraph contains a vertex of degree at most k. The following fact is easy to prove by induction :

  • A k-degenerate graph is (k+1)-choosable

Are there k-degenerate graphs that are k-choosable ? Following are some known results and open problems :

  • Every bipartite planar graph is 3-choosable [Alon & Tarsi '92]. It is easy to prove that every bipartite planar graph is 3-degenerate.
  • Every planar is 5-choosable [Thomassen '94]. Note that every planar graph is 5-degenerate. There are planar graphs which are not 4-choosable [Voigt '93].
  • Every planar graph of girth at least 5 is 3-choosable. This implies grotzsch’s theorem in a very cute way [Thomassen '03]. There are planar graphs of girth 4 which are not 3-choosable [Voigt '95].
  • Conjecture : Every 3-colorable planar graph is 4-choosable.

Note : A recent paper [DKT '08], presents a very short proof of Grotzsch’s theorem and a linear-time algorithm for 3-coloring such graphs.

References :

  • [Alon & Tarsi '92] N. Alon, M. Tarsi: Colorings and orientations of graphs. Combinatorica 12(2): 125-134 (1992)
  • [Thomassen '94] C. Thomassen: Every Planar Graph Is 5-Choosable. J. Comb. Theory, Ser. B 62(1): 180-181 (1994)
  • [Voigt '93] M. Voigt: List colourings of planar graphs. Discrete Mathematics 120(1-3): 215-219 (1993)
  • [Thomassen '03] C. Thomassen: A short list color proof of Grötzsch’s theorem. J. Comb. Theory, Ser. B 88(1): 189-192 (2003)
  • [Voigt '95] M. Voigt : A not 3-choosable planar graph without 3-cycles. Discrete Mathematics 146(1-3): 325-328 (1995)
  • [DKT '08] Z. Dvorak and K. Kawarabayashi and R. Thomas : Three-coloring triangle-free planar graphs in linear time. To appear in SODA 09.

P vs NP on arxiv

March 28, 2009 2:00 am

P vs NP on arxiv

There is a paper on Arxiv claiming that P != NP.
Here are the other papers on DBLP from this author.

Friendly Numbers

March 28, 2009 2:00 am

Friendly Numbers

Pythagoras said “220 and 284 are friendly numbers” !! These numbers have a special property : Each is equal to the sum of the other’s proper divisors. Proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 (they sum to 284). Proper divisors of 284 are 1, 2, 4, 71 and 142 (they sum to 220). More example include (1184, 1210), (17296, 18416). It is not known whether there are infinitely many friendly numbers. Twin primes are a pair of consecutive odd numbers both of which are prime.

  • Theorem : There are infinitely many friendly numbers. (proof)
  • Conjecture : There are infinitely many twin primes.

IMO 2008 Results

March 28, 2009 2:00 am

IMO 2008 Results

49th International Mathematical Olympiad results are announced. Three participants secured full marks, as opposed to 2007, when nobody scored 42.

SODA 2009 accepted papers

March 28, 2009 2:00 am

SODA 2009 accepted papers

SODA 2009 accepted papers list is here.
Here is a list with the abstracts.

ISAAC 2008 accepted papers

March 28, 2009 2:00 am

ISAAC 2008 accepted papers

ISAAC 2008 accepted papers list is here.

The "Bipasha" factor

March 27, 2009 8:36 pm

The "Bipasha" factor

Counting has begun in six states. Strangely, looks like Congress has not been hit as badly due to 26/11 at Mumbai. Congress leading in Delhi (an urban stronghold), Rajasthan and Mizoram.

“Experts” on CNN-IBN are attributing it to the “Bipasha” factor. I had a tough time figuring out what this factor really means. Was Bipasha Basu campaigning for the Congress? Was Bipasha the name of the daughter of some politician, and was campaigning vigorously for the Congress?

Now I find that the “Bipasha” factor is the “Bijli, Pani and Sadak” factor. The electricity, water and roads factor. Congress has delivered Bipasha in Delhi, and seems to be making a strong comeback.

Free hugs Mumbai

March 27, 2009 8:36 pm

Free hugs Mumbai

Bravo Vinit Mehta. Take a bow.

We will get through this, as long as have this spirit within us.

A Mahatma

March 27, 2009 8:36 pm

A Mahatma

This is unprecedented. India is seeing the beginnings of a people’s movement, like it has not seen in the recent past.

Two years ago, the reservation furore was turning into a major students movement, but stopped short of transcending students and moving on to become a full-fledged people’s movement.

This time, India is shocked. No-one in the country wants to sit and watch. We are tired of our political establishment, and we want change. The whole country is outraged. Riveting speeches from public personalities, stunned silence from intellectuals, and angst from students and the youth: this is what the last few days have seen.

Yet, I know it will die down. Life will go on as usual. Why do I feel so?

A great movement needs a great leader. Independence had the Mahatma. He will not be back, but do we have anyone who has the moral rectitude to stand up and declare that they will be the people’s voice in this movement?

Never mind Bapu. Do we have one Kripalani, one Vinoda Bhave or one Jaiprakash Narayan who can take these emotions and turn it into a revolution?

I do not believe that we have even one leader who has the courage and strength to change our democracy. Intellectual voices like Arun Shourie and Jairam Ramesh don’t have the mass appeal to connect with the millions. Mass leaders like Narendra Modi, Mayawati and Nitish Kumar, while good leaders in their own right, are not driven by a fervent sense of patriotism and national gain. Further, intellectual voices like MS Swaminathan and Abdul Kalam do not have the faintest idea what politics is all about.

Unfortunately, the last standing great politician of moral standing died before this episode subsided: VP Singh.

It’s sad. Just knowing that this too shall pass, is quite a painful thought.

We all know of our courageous army and a few choice civil servants who are still driven by a need to do public good. The army can even give its life for the country. But they still do not give us that one leader who can change India as we know it. One man, who needs both political acumen and a sense of social justice. Not motivated by the greed of money or power, but just motivated by a vision: to see an India where every Indian is safe, and every successive government works only for the benefit of the people. As Arun Shourie says, “we cannot have a flabby State, a somnolent society and a super-efficient anti-terrorist operation.” The malaise is deep-set, and only a revolution can bring about change.

The stage is set. The podium is ready. But where is that Mahatma?

Science is conjointly fun when it goes ‘bang’

March 27, 2009 8:36 pm

Science is conjointly fun when it goes 'bang'

How many people know, Marasinghe said, that understanding Einstein’s theory of relativity is what acknowledges the global positioning system to work?

The theory explains that for an object that’s traveling very fast — say, a satellite traveling at 18,000 mph relative to the Earth’s surface — span flows slower. Because GPS receivers triangulate their location along Earth by timing the signals from the satellites, it’s critical that they adjust for tiny changes in the flow of period.

So, e=mc2 eventually led to a helpful not much gadget that says "turn left this day.”

"By the time students get to high school level, in a ritual, they are programmed to think science should be hard including not something they want to follow,” Marasinghe said.

They’re easier to reach when they’re younger, he said.

Question on a forum

March 27, 2009 8:36 pm

Question on a forum

Einstein’s relativity theory? can somebody answer my question, I dont understand.

Why is it that if something goes really fast, it looks smaller?

Why is it that the faster you go, the more time slows down? So if I went for a jog, my clock will tick slower than if I left it?

As it’s been a while since you posted and nobody’s responded, maybe you want to check out Coursework.Info - the UK’s largest academic coursework library.

They have over 130,000 coursework documents at GCSE, A Level and University level.

They submit all their documents to Turnitin anti-plagiarism software and the site is used and approved by hundreds of thousands of UK teachers and students.

General Theory of Relativity

March 27, 2009 8:36 pm

General Theory of Relativity

Posterior 1905, Einstein advanced working in full three of his works in the 1905 papers. He assembled prominent contributions to the quantum theory, while increasingly he sought to extend the special theory of relativity to phenomena involving increasing speed. The key to an elaboration emerged in 1907 with the principle of equivalence, in which gravitational speeding up was owned a priori indistinguishable from acceleration caused by mechanical forces; gravitational mass was therefore identical regardless of inertial mass. Einstein elevated this identity, which is implicit in the work of Isaac Newton, to a guiding principle in his attempts to explain both electromagnetic and gravitational quickening according to one set of physical laws. In 1907 he proposed that if mass were equivalent to energy, then the principle of equivalence required that gravitational mass would interact regardless of the apparent mass of electromagnetic radiation, which includes light. By 1911, Einstein was able to expand preliminary predictions approximately how a ray of light from a distant star, passing near the Sun, would exist to be attracted, or bent slightly, in the direction of the Sun’s mass. At the same time, light radiated from the Sun would interact regardless of the Sun’s mass, resulting in a slight change toward the infrared end of the Sun’s optical spectrum. At this juncture Einstein moreover knew that any new theory of gravitation would benefit from to account for a small but persistent anomaly in the perihelion motion of the planet Mercury.

Theory of Relativity Passes Another Test

March 27, 2009 8:36 pm

Theory of Relativity Passes Another Test

Einstein’s theory of General Relativity has been around for 93 years, also it barely keeps hanging in there. Despite advances in technology has come the ability to put the theory under some scrutiny. Earlier, taking advantage of a unique cosmic coincidence, inclusive of a pretty darn good telescope, astronomers looked at the strong gravity from a pair of superdense neutron celebrities furthermore measured an actualize predicted by General Relativity. The theory came through regardless of flying colors.
Einstein’s 1915 theory predicted that in a close system of two very massive objects, such as neutron stars, one object’s gravitational tug, also an bring off of its spinning around its axis, should cause the spin axis of the other to wobble, or precess. Studies of other pulsars in binary systems had indicated that such wobbling occurred, however could not make precise measurements of the amount of wobbling.
“Measuring the amount of wobbling is what tests the details of Einstein’s theory together with stocks a benchmark that any alternative gravitational theories must meet,” said Scott Ransom of the National Radio Astronomy Observatory.
The astronomers applied the Country-wide Science Foundation’s Robert C. Byrd Green Bank Telescope (GBT) to make a four-year study of a double-star system unlike any other known in the Universe. The system is a pair of neutron stars, both of which are seen as pulsars that emit lighthouse-like beams of radio waves.
“Of about 1700 known pulsars, this is the only case where two pulsars are in orbit around each other,” said Rene Breton, a graduate student at McGill University in Montreal, Canada. As well as, the celebrities’ orbital plane is aligned just about perfectly despite their line of sight to the Earth, so that one passes below a doughnut-shaped region of ionized gas surrounding the other, eclipsing the signal from the pulsar in postliminary.
Animation of double pulsar system
The eclipses allowed the astronomers to pin down the geometry of the double-pulsar system including track changes in the orientation of the spin axis of one of them. As one pulsar’s spin axis slowly moved, the pattern of signal blockages as the other passed behind it along changed. The signal from the pulsar in ensuign is absorbed by the ionized gas in the other’s magnetosphere.
The pair of pulsars studied despite the GBT is almost 1700 light-years from Earth. The average distance between the two is only approximately twice the distance from the Earth to the Moon. The two orbit each other in merely under two along with a half hours.
“A system like this, despite two very massive objects very close to each other, is precisely the kind of extreme ‘cosmic laboratory’ needed to test Einstein’s prediction,” said Victoria Kaspi, leader of McGill University’s Pulsar Group.
Theories of gravity don’t differ significantly in “ordinary” regions of space such as our own Solar System. In regions of extremely strong gravity fields, such as near a pair of close, massive objects, while, differences are expected to motion picture up. In the binary-pulsar study, General Relativity “passed the test” provided by such an extreme environment, the scientists said.
“It’s not quite right to say that we take advantage of today ‘proven’ General Relativity,” Breton said. “Yet, so far, Einstein’s theory has passed total the tests that have been conducted, over and above ours.”