A Really Nice Talk About PDE, Numerics (and Pyramids)

My previous post recommended a really nice talk by Jonathan Israel about human rights. Here is the link again. It is very recommended. Actually, I was in the audience and after the lecture, at the reception,  I came to the lecturer to compliment him for the talk, except that I approached a different, rather similar looking, person.

I am not going to make it a habit on this blog to recommend good videotaped lectures available on the Internet (unless this new Genre will lead to a sky-rocketing rating), but, just one more time, let me recommend you a really really nice lecture. It is a lecture with a scary title High order FEM-approximation on pyramids, by Nilima Nigam. Click on the picture to go directly to the lecture or click here. (And if you want to see the picture enlarged, click here.)

The first part is about “What is a PDE,” and it is an eye opener for people with little familiarity of PDEs (like me) and perhaps also an eye opener for PDE professionals on how to introduce them. And then it goes on to explain what finite element methods are, and about the recent finite element exterior calculus.

The 1789 Declaration of the Rights of Man

Today (April 27, 2012) it is precisely 213 years 7 months, and 29 days to the completion of the declaration of the rights of man, which makes it a perfect occasion to celebrate this remarkable human creation.

Here is a beautiful lecture by Jonathan Israel about the history of basic human rights:

The History of Basic Human Rights: The Declaration of the Rights of Man, 1789

Galvin’s Proof of Dinitz’s Conjecture

Dinitz’ conjecture

The following theorem was conjectured by Jeff Dinitz in 1979 and proved by Fred Galvin in 1994:

Theorem: Consider an n by n square table such that in each cell (i,j) you have a set A_{i,j} with n or more elements. Then it is possible to choose elements a_{ij} from A_{ij} such that the chosen elements in every row and in every colummn are distinct.

Special case: if all A_{ij} are the same set, say {1,2,…,n} then this is possible. Such a choice is called a Latin square for example a_{ij}=i+j({\rm mod} n).

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Here are a few remarks before we go ahead with Galvin’s proof:

1) The Theorem is about graph-coloring from  lists of colors, or briefly list-coloring. Given a graph G with n vertices and a list of colors A_i for vertex i we ask for a proper coloring of the graph such that vertex i is colored by an element of A_i. (A proper coloring is a coloring such that two djacent vertices have different colors.)

The list chromatic number of a graph G is the smallest number k such that G can be colored from any lists of colors, where every A_i has k elements.

2) We consider the graph G whose vertices are the pairs (i,j) and two vertices are adgacent if one of their coordinates agree. This graph is the line graph of the complete bipartite graph K_{n,n}. The line graph L(H) of a graph H is the graph whose vertices correspond to the edges of H and two vertices are adjacent if the corresponding edges share a vertex.

3) Vizing proved that the chromatic number of the line graph L(H) is at most one more than the maximum degree of H. He conjectured that this is also true for list coloring. A bolder version asserts that for every line-graph G the list chromatic number equals the chromatic number. Dinits’s conjecture is the special case (of the bolder version) where G is the line graph of the complete bipartite graph K_{n,n}. The proof demonstrates Vizing’s conjecture for the line graph of every bipartite graph.

4) Shortly before Galvin, Jeannette Janssen gave an amazing proof for a slightly weaker statement where in each square you allow n+1 colors.  (She proved the Dinitz conjecture for rectangular arrays.) Janssen applied  a theorem of Alon and Tarsi, who used the “polynomial method” to obtain a powerful necessary condition for list coloring.

5) Here are now (or when I will be able to find them later) links to Galvin’s paper, to Janssen’s paper, to Alon-Tarsi’s paper,  to expositions by Barry Cipra and by Doron Zeilberger and to a short self-contained version of the proof by Tomaž Slivnik.

Galvin’s proof

Galvin’s ingenious proof of Dinitz’ the conjecture combines two known theorems which are quite easy themselves.

For a directed graph G an induced subgraph is a subgraph spanned by a subset of the set of vertices of G. A kernel in a directed graph is an independent and absorbant set of vertices. I.e., it is a set of vertices W such that there is no edge between any two vertices in W, and from every vertex not in W there is an edge directed from it to a vertex in W.

Lemma 1 (Bondy, Boppana, Siegal): (mentioned e.g. in the paper by Alon and Tarsi)

Continue reading

Greg Kuperberg: It is in NP to Tell if a Knot is Knotted! (under GRH!)

Wolfgang Haken found an algorithm to tell if a knot is trivial, and, more generally with Hemion, if two knots are equivalent.

Joel Hass, Jeff Lagarias and Nick Pippinger proved in 1999 that telling that a knot is unknotted is in NP. This is a major result!

An outstanding problem for many years was to determine if telling that a knot is unknotted is in coNP or equivalently if telling that a knot is nontrivial is in NP as well. A few month ago Greg Kuperberg proved it under GRH (the generalized Riemann hypothesis)! Amazing! Kuperberg ingenious short proof is based on a recent important knot-theoretic result by Kronheimer and Mrowka combined with computational complexity result by Koiran (discussed in the section “from Primes to Complexity”over this GLL’s post).

There were several results in knot theory in recent years that gradually showed that several invariants (related, generally speaking, to Jones polynomials but more detailed, e.g., Khovanov homology,) are enough to tell if a knot is trivial. I am not so sure about how this fascinating story goes.

An earlier, different,  approach (via the Thurston norm) from 2002 to showing that verifying that a knot is trivial is in coNP was by Ian Agol.   

It is very interesting if the dependence on GRH can be removed. Of course, a major problem is if telling if a knot is trivial is in P. Showing that the problem is in BQP will also be great.

Eralier,  in a SODA 2005 article, Hara, Tani, and Yamamoto proved  that unknotting is in AM \cap coAM. As mentioned in the comments the argument was incomplete. (One thing I learned from Greg’s preprint is that there is a preprint by Chad Musick who is describing a polynomial-time algorithm for testing if a knot is trivial. His work is based on a knot-invariant called “the crumble,” and its status is unclear at present.)

I am not sure what is the complexity for telling if two knots are equivalent. Haken and Hemion proved that it is decidable. Telling if a knot is trivial feels a little like PRIMALITY while telling two knots apart feels a little like FACTORING. Here is a survey article by Joel Hass on the computability and complexity of knots and 3-manifolds equivalence. It looks that the algorithmic theory of knots is related to both coltures of 3-dim topology, the one related to structural results, combinatorial group theory, geometrization etc, and the other related to invariants and physics, and this is nice. See also the post over GLL entitled “What makes a knot knotty.”

And here is Greg’s description of his ingenious proof. (It is not as easy as the description suggests.) Reading Greg’s short page paper is  recommended.

Exciting News on Three Dimensional Manifolds

The Virtually Haken Conjecture

A Haken 3-manifold is a compact 3-dimensional manifold M which is irreducible (in a certain strong sense) but contains an incompressible surface S. (An embedded surface S is incompressible if the embedding indices an injection of its fundamental group to the fundamental group of M. A 3-manifold is virtually finite Haken  if it has a finite cover which is Haken. (This is a typical way how the word “virtually” occurs in algebra and topology.)

The virtually Haken conjecture states that every compact, orientable, irreducible 3-dimensional manifold with infinite fundamental group is virtually Haken. The big news is that Ian Agol has just announced the proof of the virtually Haken conjecture!

Danny Calegary have just wrote three detailed posts about it over his blog “Geometry and the Imagination”:  Agol’s Virtual Haken Theorem (part 1),  Agol’s Virtual Haken Theorem (part 2): Agol-Groves-Manning strike back, and Agol’s Virtual Haken Theorem (part 3): return of the hierarchies. (Everything I say is taken from there.)

To quote Danny:

I think it is no overstatement to say that this marks the end of an era in 3-manifold topology, since the proof ties up just about every loose end left over on the list of problems in 3-manifold topology from Thurston’s famous Bulletin article (with the exception of problem 23 — to show that volumes of closed hyperbolic 3-manifolds are not rationally related — which is very close to some famous open problems in number theory).

Here are also few relevant posts from the blog: Low dimensional topology. A post about Wise conjecture  (that Agol proved)  with references and links;   An earlier post on Wise’s work; A post VHC post; Update (August ’14): Here is a post by Tim Gowers on Agol’s lecture at ICM2014. The videotaped lecture can be found here. Ian’s ICM paper can be found here. Dani Wises’s ICM talk is here.

Problems 16-18 in Thurston’s Bulletin paper.

A whole array of conjectures and a whole array of results: Wise, Haglund-Wise, Bergeron-Wise, Sageev, Kahn-Markovic, …

Perleman’s geometrization theorem reduces the conjecture to the case of hyperbolic manifolds. Continue reading