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 with n or more elements. Then it is possible to choose elements from such that the chosen elements in every row and in every colummn are distinct.

Special case: if all are the same set, say {1,2,…,n} then this is possible. Such a choice is called a Latin square for example .

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 for vertex we ask for a proper coloring of the graph such that vertex i is colored by an element of . (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 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 . 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 . 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)

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 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 Ion 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;

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.

גאומטריה, שוויון ומזל

דברי תודה בשם מקבלי פרס רוטשילד 2012

אדוני שר החינוך, הלורד רוטשילד, פרופסור קולברג, עמיתי כלת וחתני הפרס, גבירותי ורבותי

אפתח בתודה מקרב לב בשם מקבלי הפרס לקרן רוטשילד. פרס רוטשילד הוא אות חשוב ומרגש להערכה של החברה שלנו למדע, והבחירה בנו היא הכרה מחממת לב מצד עמיתנו, לעבודתנו על פני עשורים רבים. פרס רוטשילד הוא ביטוי, אחד בין רבים, לשותפות האמיצה של משפחת רוטשילד עם מדינת ישראל, החברה הישראלית, ומיטב ערכיה.

הרשו לי לשתף אתכם תחילה במספר תמונות שעלו אצלי כשנודע לי על הפרס ועל הטקס שעתיד להתקיים במשכן הכנסת.

תמונה ראשונה הקשורה בשם רוטשילד. שם שהפך בעם ובמדינה שלנו למושג שטבוע עמוק כמו הרצל או ביאליק. כאשר אנו מפזמים את השיר “לו הייתי רוטשילד”, שמקורו בסיפור באידיש של שלום עליכם מלפני מאה ועשר שנים, הרי שהשם רוטשילד הוא מטאפורה לאידיאל בלתי מושג. והינה רק בקיץ האחרון נוסף נדבך לשם רוטשילד, כאשר המחאה החברתית ההמונית שהדהימה אותנו צמחה בשדרות רוטשילד.

תמונה שנייה, קשורה לילדותי בירושלים כאשר גרתי עם אבי חנוך ואימי כרמלה ברחוב קטן מסילת ישרים שמו, שם שיחקתי עם אחותי תמי וחברי ילדותי איציק ואלי. בקצה הרחוב היה בית כנסת בקומה שנייה של בית יתומים, ובו, בשמחת תורה, שימחו אותנו הילדים האחים רובי ולייזי וחבר שלהם  שאף הפליא לרקוד עם מטאטא מאוזן על סנטרו. האח הבכור , חבר הכנסת רובי ריבלין, הוא יושב ראש הכנסת המארחת אותנו היום.

תמונה שלישית היא התמונה של גבעת רם, גבעה ברת מזל, אשר בה שוכנת האוניברסיטה שלנו, הכנסת ומשרדי הממשלה, בית המשפט העליון ומוזיאון ישראל. גבעה בה התחלתי את לימודי המתמטיקה כנער, ובה סיימתי את לימודי הדוקטוראט בהדרכת פרופסור מיכה פרלס, כרבים מעמיתי בתחום הקומבינטוריקה. גבעה בה ביליתי את רוב זמני בארבעים השנים האחרונות.

מאד גאה אני בעמיתי לקבלת הפרס. הנה אך לפני אלפיים ומאתיים שנים יצאה התרבות היהודית  בהתרסה מול התרבות הדומיננטית היוונית ועדיין רב הנסתר בקשרים בין תרבויות אלה. ועכשיו החוקרים שלנו, ובהם עמיתי כלת וחתן הפרס במדעי הרוח, מפליאים במחקריהם הן על תרבותינו שלנו לאורך הדורות והן על התרבות היוונית העתיקה. עמיתי שני חתני הפרס במדעים המדוייקים תרמו תרומות נפלאות להבנת החיים, להבנת מחלות  וריפוים ולהקלת סבל וכאב.

ומה ניתן לאמר על תרומת המתמטיקאי? לא הרבה ניתן להסביר. יש המדמים מתמטיקאים לקומפוזיטורים שמעבירים ביניהם פרטיטורות מסובכות הממלאות אותם סיפוק ושמחה, וכאשר הם מנסים להשמיע את המוסיקה שלהם ברבים הם נתקלים ברתיעה ובבהלה.  אגיד אם כן רק מספר מילים על שלושה מושגים ממתמטיקה, שאף אני עוסק בהם, ושיתכן שידברו אליכם גם אם אינכם מתמטיקאים: גאומטריה, שוויון, ומזל.

הגאומטריה היא העתיקה במקצועות המתמטיקה. מקורה בתרבות היוונית, חשיבות ניכרת לה בקבלה, וערכה רב בחקר החיים ומדעי הפיסיקה והכימיה. בתיאור עבודתי מוזכרת צורה גאומטרית שמצאתי עם עמית למחקר במימד 1350, ואשר הפריכה השערה ידועה שרוב המתמטיקאים האמינו בה עשרות שנים. אבל מה בכלל המשמעות של גאומטריה במימדים גבוהים? דבריו של רבי מנחם מנדל מקוצק  רלוונטיים גם למימדים גבוהים וגם למושגים אחרים מהמתמטיקה ומהמדע בכלל שמתנגשים עם המציאות כפי שהיא נראית לנו, וכך אמר: “כל מה שאדם רואה בעיניו הגַשמיות אינו מציאות כלל. רק מה שהוא רואה בעיניו השִכליות, זוהי מציאות!”

אעבור עתה למושג השוויון. אין דבר המזוהה יותר עם המתמטיקה משוויונים ומשוואות, ומושג השוויון והבנתו קשורים לתחומי המחקר של כולנו.  הביטו בבקשה על הצורה שבידי – האיקוסהדר. גוף זה נקרא פאון. הוא  אחד מחמשת הפאונים המשוכללים האפלטוניים. אם נחבר את מספר הקדקדים (12) למספר הפאות (20) ונחסיר את מספר הצלעות (או המקצועות) (30) נקבל שתיים.  המתמטיקאי לאונרד אוילר, שחי במאה השמונה עשרה, גילה שכך הדבר לכל פאון ופאון, ויש אף המייחסים שוויון זה לרנה דקארט, שחי כמאה שנים לפני אוילר.  עובדה זאת, הנקראת השויון של אוילר, יכולה מרחוק להיראות בלתי מעניינת וחסרת משמעות, אבל היא הבסיס לתחומים שלמים במתמטיקה ופיסיקה, ואף חלק ממחקרי עוסק בשוויונות דומים.

כאשר מדובר בשוויון הרשו לי, גבירותי ורבותי, לאמר דבר מענייני היום ולהזכיר, כאן בביתה של הכנסת שלנו, שאין תחליף לשוויון. אין תחליף לשוויון כבסיס לדמוקרטיה שלנו, ואין תחליף לשוויון כבסיס למערכת המשפטית שלנו, ואין תחליף לשוויון כערך בחברה ובכלכלה שלנו.

ולבסוף כמה מילים על מזל. גם מזל הוא מושג שמתמטיקאים, ואני בתוכם, עוסקים בו, והבנתו קשורה לכל תחומי חיינו. להבנה ולחקר המזל יש גם קשר לנושאי המחקר של כל עמיתי לפרס. המחקר שלי בתורת ההסתברות, העוסקת במזל, קשור למה שקרוי תופעות סף אשר בהם שינוי קטן בהסתברויות משנה באופן ניכר את התוצאה.

כמה פשוט היה העולם ללא מזל ואי ודאות, וכמה משעמם היה. כאשר בירך אותי יושב ראש המחלקה במזל טוב לרגל הזכייה בפּרס, ציין שבודאי הפּרס הוא ביטוי של עבודה קשה ולא של מזל.  חבר המחלקה ישראל אומן הגיב מייד שבמקרה שלי דווקא מגיע קרדיט רב למזל, כלומר לרעייתי מזל. ואכן מזל, מזי, ומשפחתי אינם רק שותפים להישגים, אלא מעבר לכך, הם אותו אי של ודאות בחיי הנותן להישגים את משמעותם.

מזל טוב לכולנו ותודה רבה.

Satoshi Murai and Eran Nevo proved the Generalized Lower Bound Conjecture.

Satoshi Murai and Eran Nevo have just proved the 1971 generalized lower bound conjecture of McMullen and Walkup, in their  paper On the generalized lower bound conjecture for polytopes and spheres . Let me tell you a little about it. For more background see the post: How the g-conjecture came about.

Face numbers and h-numbers

Let P be a (d-1)-dimensional simplicial polytope and let be the number of -dimensional faces of P. The -vector (face vector) of P is the vector .

Face numbers of simplicial d-polytopes  are nicely expressed via certain linear combinations called the h-numbers. Those are defined by the relation:

What’s called “Stanley’s trick” is a convenient way to practically compute one from the other, as illustrated in the difference table below, taken from Ziegler’s book `Lectures on Polytopes’, p.251:

1

1           6

1          5            12

1          4           7            8

h= (1        3          3            1)

Here, we start with the -vector of the Octahedron (1,6,12,8) (bold face entries) and take differences as shown in this picture to end with the -vector (1,3,3,1).

The Euler-Poincare relation asserts that . More is true. The Dehn-Sommerville relations state that is symmetric, i.e. for every .

The generalized lower bound conjecture

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture (GLBC):

Let P be a simplicial d-polytope. Then

(A) the h-vector of P,  satisfies .

(B) If for some then can be triangulated without introducing simplices of dimension .

The first part of the conjecture was solved by Stanley in 1980 using the Hard Lefschetz theorem for toric varieties. This was part of the g-theorem that we discussed extensively in a series of posts (I, I’, II, III, B). In their paper, Murai and Nevo give a proof of part (B). This is remarkable!

Earlier posts on the g-conjecture:

I: (Eran Nevo) The g-conjecture I

I’ How the g-conjecture came about

II (Eran Nevo) The g-conjecture II: The commutative-algebra connection

III (Eran Nevo) The g-conjecture III: Algebraic shifting

B: Billerafest

Which Street is More Important: Canner Street or Cold Spring Street

Is it possible that Cold Spring Street is as important as Canner Street?

I knew Canner Street from my earlier visits to Yale but Cold Spring Street was new to me. Naturally, I assumed that Canner Street was the important one among the two. One day, however, while walking home, I crossed Cold Spring Street and it seemed as wide and as impressive as Canner Street. Perhaps, I thought, Cold Street is as important as Canner Street, and just the fact that I did not hear about Cold Spring Street earlier made me think otherwise. This was an interesting novel thought, but soon enough I saw one major problem: I was actually walking in Canner Street, so it was not surprising that it looked as wide as Canner street. I quickly went to the real Cold Spring Street and then it also looked indeed as wide and as impressive as Canner Street. But I was fully aware that this impression might be biased by the previous one.

Some evidence that Canner Street is more important is that in the Whitney-Canner crossing there are traffic lights while in the Whitney-Cold-Spring crossing there is only a flashing yellow light. However, when you go on Orange Street the situation is reversed: The Orange/Canner crossing is a flashing yellow light and the Cold Spring Orange crossing has full-fledged traffic lights. You may say that prominent streets like Whitney and Orange themselves are more important than both Canner and Cold Spring streets. Be it as it may be, in this post we discuss only horizontal streets, and don’t touch at all on the importance of vertical streets. In fact, we compare only two streets, Canner Street and Cold Spring Street.

The following year my wife visited me at Yale and I told her about my inquiries regarding the relative importance of Cold Spring Street and Canner Street. My wife listened carefully, and even added one interesting piece of evidence that I did not consider before. My own street, Everit street (a small vertical street famous for hosting Yale’s president Rick Levin and the famous economist John G.), crossed Cold Spring Street but ended at Canner Street. My wife thought that this piece of evidence supported my feeling about the importance of Cold Spring street. I was not sure about it; to me it looks that Everit ending at Canner street rather than crossing  it,  gives Canner street some edge.

At some point I decided to test matters scientifically and I measured in steps the width of Canner Street. But I returned to Israel before making a similar measurenemt at Cold Spring Street and by now I forgot the outcomes.

Of course, we can say that Canner Street is the more important on its Whitney side and the less important on its Orange side. But this answer simply does not face the real problem. Perhaps an opinion poll can help.

At the end, after some years, I came to the conclusion that Canner Street is more important than Cold Spring Street because it extends beyond Whitney while Canner Street does not. (But please dont be influenced by me.)

Michal Linial: No Witches in Portugal

It gives me great pride to present:

 

Michal Linial:  March 2012

No witches in Portugal

Landing in LISBOA, Portugal last night. I need to get to my hotel in Cascais. The nice lady in the tourist information ordered a taxi and happily said: “Do not worry, our drivers speak excellent English.

Five minutes later my driver arrived, a huge person, nicely dressed with a fancy nice black car. “To Cascais, What is the price” I asked in a fluent English.  Well, it depends he replied…

My huge driver, was very fluent in English as promised… Then he starts… Three years ago I had a ski accident, at that time I was much heavier… I was wondering how such information might be relevant to our trip… My driver continues: “From the time of the accident my leg is not the same. This is why I bought this car with a “gear” instead of an automatic transmission, so I can practice my left leg. Most of time I can move it, but I still do not feel it when it is cold”… “Is it cold today?” I asked. No, today it is fine. Yesterday it was cold.

How long is it to Cascais? I was asking. My driver relied honestly: “it depends on the road”… Oh, I said… waiting for an explanation. It took a minute for him to explain: “You know, I always drive by my feelings. Sometime, I have a feeling that it is not good to take the freeway. Today I have this feeling. “OK, it is best that you listen to your feelings”, I relied quietly. He continues: “You know, there are no witches in Portugal, but it is better to listen to them”. Of course, I said.

You know he continue, my brother in law who was a driver in our taxi company had a bad feeling 4 months ago when he took the small road instead of the highway, and indeed he died. A truck crushed him. But the passenger, a British person that was in the car was not hurt. The passenger had his seat belt fasten, like you… Do you want me to show you where he died?, it is on the way to the hotel, he insisted. Sure I replied. If it is on the way, and you feels that we should not take the highway, let’s go on the other road…

We drove on a neglected road. It was not too cold… My huge driver mentioned me the spot where his brother in law died…  We are now 10 min from the hotel he updated me. But I missed the entrance. You know, he continued, once I drove with my mother, I missed the entrance to the road. Then, I knew that I should not get into this road. Do you mind that I will drop you here? it is no more than 200 meters to your hotel. I happily paid the 60 Euro, another tip for 10 Euro for the good witch that was with us.  

While I was walking with my luggage on the hill to the hotel, a taxi was stopping behind me. It was my big driver again… He said: I forgot to give you my card. Please call me when you want to go back to the airport. it will be only 30 Euro. We can take the highway. I am still in Portugal for another 2 days. I will call him if it will not be too cold.

• 

Updates, Boolean Functions Conference, and a Surprising Application to Polytope Theory

The Debate continues

The debate between Aram Harrow and me on Godel Lost letter and P=NP (GLL) regarding quantum fault tolerance continues. The first post entitled Perpetual  motions of the 21th century featured mainly my work, with a short response by Aram. Aram posted two of his three rebuttal posts which included also short rejoiners by me. Aram’s first post entitled Flying machines of the 21th century dealt with the question “How can it be that quantum error correction is impossible while classical error correction is possible.” Aram’s  second post entitled Nature does not conspire deals with the issue of malicious correlated errors.  A third post by Aram is coming and  the discussion is quite interesting. Stay tuned. In between our posts GLL had several other related posts like Is this a quantum computer? on how to tell that you really have a genuine quantum computer , and Quantum ground day that summarized the comments to the first post.

Virgin Island Boolean Functions

In the beginning of February I spend a week in a great symposium on Analysis of Boolean Functions, one among several conferences supported  by the Simons foundation, that took place at St. John of the Virgin Islands.

Irit Dinur and me

Ryan O’Donnell who along with Elchanan Mossel and Krzysztof Oleszkiewicz (the team of “majority is stablest” theorem) organized the meeting, live blogged about it on his blog. There are also planned scribes of the lectures and videos. I posed the following problem (which arose naturally from works presented in the meeting): What can be said about circuits with n inputs representing n Gaussian random variables, and gates of the form: linear functions, max and min.

A surprising application of a theorem on convex polytopes.

(Told to me by Moritz Schmitt and Gunter Ziegler)

A theorem I proved with Peter Kleinschmidt and Gunter Meisinger asserts that every rational polytope of dimension d>8 contains a 3-face with at most 78 vertices or 78 facets. (A later theorem of Karu shows that our proof applies to all polytopes.) You would not expect to find a real life application for such a theorem. But a surprising application has just been given.

Before talking about the application let me say a few more words about the theorem. The point is that there is a finite list of 3-polytopes so that every polytope of a large enough dimension (as it turns out, eight or more) has a 3-face in the list. It is conjectured that a similar theorem holds for k-faces, and  it is also conjectured that if the dimension is sufficiently high you can reduce the list to two polytopes: the simplex and the cube. These conjectures are still open. (See this post  for related open problems about polytopes.) For k=2, it follows from Euler’s theorem that every three-dimensional polytope contains a face which is a triangle, quadrangle, or pentagon, and in dimension five and up, every polytope has a 2-face which is a triangle or a rectangle.

A Discussion and a Debate

Heavier than air flight of the 21 century?

The very first post on this blog entitled “Combinatorics, Mathematics, Academics, Polemics, …” asked the question “Are mathematical debates possible?” We also had posts devoted to debates and to controversies.

A few days ago, the first post in a discussion between Aram Harrow, a brilliant computer scientists and quantum information researcher (and a decorated debator), and myself on quantum error correction was launched in Dick Lipton and Ken Regan’s big-league blog, Gödel’s Lost Letter and P=NP.

The central question we would like to discuss is:

Are universal quantum computers based on quantum error correction possible.

In preparation for the public posts, Ken, Aram, Dick, and me are having very fruitful and interesting email discussion on this and related matters, and also the post itself have already led to very interesting comments. Ken is doing marvels in editing what we write.

Dick opened the post by talking on perpetual motion machines which is ingenious because it challenges both sides of the discussion. Perpetual motion turned out to be impossible: will quantum computers enjoy the same fate? On the other hand (and closer to the issue at hand), an argument against quantum mechanics based on the impossibility of perpetual motion by no other than Einstein turned out to be false, are skeptical ideas to quantum computers just as bogus? (The answer could be yes to both questions.) Some people claimed that heavier-than-air flight might is a better analogy. Sure, perhaps it is better.

But, of course, analogies with many human endeavors can be made, and for these endeavors, some went one way, and some went the other way, and for some we don’t know.

Although this event is declared as a debate, I would like to think about it as a discussion. In the time scale of such a discussion what we can hope for is to better understand each other positions, and, not less important, to better understand our own positions.  (Maybe I will comment here about some meta aspects of this developing discussion/debate.)

A real debate

A real emerging debate is if we (scientists) should boycott Elsevier. I tend to be against such an action, and especially against including refereeing papers for journals published by Elsevier as part of the boycott. I liked, generally speaking,  Gowers’s critical post on Elsevier, but the winds of war and associated rhetoric are not to my liking.  The universities are quite powerful, and they deal, negotiate and struggle with scientific publishers, and other similar bodies, on a regular  basis. I tend to think that the community of scientists should not be part of such struggles and that such involvement will harm the community and science. This is a real debate! But it looks almost over.  Many scientists joined the boycott and not many opposing opinions were made. It looks that we will have a little war and see some action. Exciting, as ever.

Fractional Sylvester-Gallai

Avi Wigderson was in town and gave a beautiful talk about an extension of Sylvester-Gallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff.

Sylvester-Gallai

The Sylvester-Gallai Theorem:  Let X be a finite set of n points in an eulidean space such that for every two distinct points the line through and contains a third point . Then all points in  are contained in a line. 

I heard about this result when I took Benjy Weiss’s mathematics course for high-school students in 1970/1. a  The Sylvester-Gallai theorem was the last question marked with (*) in the first week’s homework. In one of the next meetings Benjy listened carefully to our ideas on how to prove it and then explained to us why our attempts of proving it are doomed to fail: What we tried to do only relied on the very basic incidence axioms of Euclidean geometry but the Sylvester-Gallai theorem does not hold for finite projective planes. (Sylvester conjectured the result in 1893. The first proof was given by Mechior in 1940 and Gallai proved it in 1945.)

My MO question

Befor describing the new results let me mention my third ever MathOverflow question that was about potential extensions of the G-S theorem. The question was roughly this: 

Suppose that V is an r dimensional variety embedded into n space so that if the intersection of every j-dimensional subspace with V is full dimensional then this intersection  is “complicated”. Then cannot be too large.  

I will not reproduce the full question here but only a memorable remark made by Greg Kuperberg:

If you claimed that Gil is short for Gilvester (which is a real first name although rare), then you could say that any of your results is the “Gilvester Kalai theorem”. – Greg Kuperberg Nov 24 2009 at 5:13

The result by Barak, Dvir, Wigderson and Yehudayoff

Theorem:  Let X be a finite set of n points in an eulidean space such that for every point the number of such that the line through and contains another point of is at least . Then

Some remarks:

1) The proof: The first ingredient of the proof is a translation of the theorem into a question about ranks of matrices with a certain combinatorial structure. The next thing is to observe is that when the non zero entries of the matrix are 1′s the claim is simple. The second surprising ingredient of the proof is to use scaling in order to “tame” the entries of the matrix. 

2)  The context – locally correctable codes:  A -query locally correctable -code over a field is a subspace of so that, given any element that disagrees with some in at most positions and an index , we can recover with probability 3/4 by reading at most coordinates of .  The theorem stated above imply that, for two queries,  over the real numbers (and also over the complex numbers), such codes do not exist when is large. Another context where the result is of interest is the hot area of sum product theorems and related questions in the geometry of incidences. 

3) Some open problems: Is there a more detailed structure theorem for configurations of points satisfying the condition of the theorem? Can the result be improved to ? Can a similar result be proved on locally correctable codes with more than two queries? This also translates into an interesting Sylvester-Gallai type question but it will require, Avi said, new ideas.