Coloring Simple Polytopes and Triangulations

Coloring

Edge-coloring of simple polytopes

One of the equivalent formulation of the four-color theorem asserts that:

Theorem (4CT) : Every cubic bridgeless planar graph is 3-edge colorable

So we can color the edges by three colors such that every two edges sharing a vertex are colored by different colors.

Abby Thompson asked the following question:

Question: Suppose that G is the graph of a simple d-polytope with n vertices. Suppose also that n is even (this is automatic if d is odd). Can we always properly color the edges of G with d colors?

Vising theorem reminded

Vising’s theorem asserts that a graph with maximum degree D can be edge-colored by D+1 colors. This is one of the most fundamental theorems in graph theory. (One of my ambitions for the blog is to interactively teach the proof based on a guided way toward a proof, based on Diestel’s book, that I tried in a graph theory course some years ago.) Class-one graphs are those graphs with edge chromatic number equal to the maximum degree. Those graphs that required one more color are called class-two graphs.

Moving to triangulations

Thompson asked also a more general question:

Question: Let G be a dual graph of a triangulation of the (d-1)-dimensional sphere. Suppose that G has an even number of vertices.  Is G d-edge colorable?

Grunbaum’s question and counterexample

Branko Grunbaum proposed a beautiful generalization for the 4CT: He conjectured that the dual graph of a triangulation of every two-dimensional manifold is 3-edge colorable. This conjecture was refuted in 2009 by Martin Kochol.

Triangulations in higher dimensions

A third question, even more general, posed by Thompson is: Let G be a dual graph of a triangulation of a (d-1)-dimensional manifold, d ≥ 4. Suppose that G has an even number of vertices.  Is G d-edge colorable?

Hamiltonian cycles

Coloring graph is notoriously difficult but finding a Hamiltonian cycle is even more difficult.

Tait’s conjecture and Barnette’s conjectures

Peter Tait conjectured in 1884 that every 3-connected cubic planar graph is Hamiltonian. His conjecture was disproved by William Tutte in 1946. A cubic Hamiltonian graph must be of class I and therefore Tait’s conjecture implies the 4CT. David Barnette proposed two ways to save Tait’s conjecture: one for adding the condition that all faces have an even number of edges or, equivalently that the graph is bipartite, and another, by moving up in the dimension.

Barnette’s conjecture I: Planar 3-connected cubic bipartite graphs are Hamiltonian.

Barnette’s conjecture II: Graphs of simple d-polytopes d ≥ 4 are Hamiltonian.

Barnette’s hamiltonicity conjecture in high dimension does not imply a positive answer to Thompson’s quaestion. We can still ask for the following common strengthening:  does the graph of a simple d-polytope, d 4, with an even number of vertices contain [d/2] edge-disjoint Hamiltonian cycles?

There are few more things to mention: Peter Tait made also three beautiful conjectures about knots. They were all proved, but it took a century more or less. When we move to high dimensions there are other notions of coloring and other generalizations of “Hamiltonian cycles.” You can Test Your Imagination and try to think about such notions!

Update (Dec 7): Following rupeixu’s comment I asked a question over: generalizations-of-the-four-color-theorem.

Jim Geelen, Bert Gerards, and Geoff Whittle Solved Rota’s Conjecture on Matroids

gcrota

Gian Carlo Rota

Rota’s conjecture

I just saw in the Notices of the AMS a paper by Geelen, Gerards, and Whittle where they announce and give a high level description of their recent proof of Rota’s conjecture. The 1970 conjecture asserts that for every finite field, the class of matroids representable over the field can be described by a finite list of forbidden minors. This was proved by William Tutte in 1938 for binary matroids (namely those representable over the field of two elements). For binary matroids Tutte found a single forbidden minor.  The ternary case was settled by by Bixby and by Seymour in the late 70s (four forbidden minors).  Geelen, Gerards and Kapoor proved recently that there are seven forbidden minors over a field of four elements.  The notices paper gives an excellent self-contained introduction to the conjecture.

This is a project that started in 1999 and it will probably take a couple more years to complete writing the proof. It relies on ideas from the Robertson-Seymour forbidden minor theorem for graphs. Congratulations to Jim, Bert, and Geoff!

Well, looking around I saw that this was announced in August 22’s post in a very nice group blog devoted by matroids- Matroid Union, with contributions by Dillon Mayhew, Stefan van Zwam, Peter Nelson, and Irene Pivotto. August 22? you may ask, yes! August 22, 2013. I missed the news by almost a year. It was reported also here and here  and here, and here, and here, and here!

This is a good opportunity to mention two additional conjectures by Gian-Carlo Rota. But let me ask you, dear readers, before that a little question.

Rota’s unimodality conjecture and June Huh’s work

Rota’s unimodality conjecture predicts that the coefficients of the characteristic polynomial of a matroid form a log-concave sequence. This implies that the coefficients are unimodal. A special case of the conjecture is an earlier famous conjecture (by Read) asserting that the coefficients of the chromatic polynomial of a graph are unimodal (and log-concave). This conjecture about matroids was made also around the same time by Heron and Welsh.

June Huh proved Reads’ unimodality conjecture for graphs and the more general Heron-Rota-Welsh conjecture for representable matroids for characteristic 0. Later Huh and  Eric Katz proved the case of  representable matroids for arbitrary characteristics. I already mentioned these startling results earlier and we may come back to them later.

Huh’s path to mathematics was quite amazing. He wanted to be a science-writer and accomponied Hironaka on whom he planned to write. Hironaka introduced him to mathematics in general and to algebraic geometry and this led June to study mathematics and a few years later to use deep connections between algebraic geometry and combinatorics to prove the conjecture.

Rota’s basis conjecture

Rota’s basis conjecture from the late 80’s appears to remain wide open. The problem first appeared in print in a paper by Rosa Huang and Rota. Here is a post about it also from “the matroid union.” It is the first problem in Rota’s article entitled “Ten Mathematics problems I will never solve“. Having access only to page one of the paper I can only guess what the other nine problems might be.

rota-fan

Rota’s portrait by Fan Chung Graham

 

 

My Mathematical Dialogue with Jürgen Eckhoff

Jürgen Eckhoff, Ascona 1999

Jürgen Eckhoff is a German mathematician working in the areas of convexity and combinatorics. Our mathematical paths have met a remarkable number of times. We also met quite a few times in person since our first meeting in Oberwolfach in 1982. Here is a description of my mathematical dialogue with Jürgen Eckhoff:

Summary 1) (1980) we found independently two proofs for the same conjecture; 2) (1982) I solved Eckhoff’s Conjecture; 3) Jurgen (1988) solved my conjecture; 4) We made the same conjecture (around 1990) that Andy Frohmader solved in 2007,  and finally  5) (Around 2007) We both found (I with Roy Meshulam, and Jürgen with Klaus Peter Nischke) extensions to Amenta’s Helly type theorems that both imply a topological version.

(A 2009 KTH lecture based on this post or vice versa is announced here.)

Let me start from the end: 

5. 2007 – Eckhoff and I  both find related extensions to Amenta’s theorem.

Nina Amenta

Nina Amenta proved a remarkable extension of Helly’s theorem. Let \cal F be a finite family with the following property:

(a) Every member of \cal F is the union of at most r pairwise disjoint compact convex sets.

(b) So is every intersection of members of \cal F.

(c) |{\cal F}| > r(d+1).

If every r(d+1) members of \cal F has a point in common, then all members of \cal F have a point in common!

The case r=1 is Helly’s theorem, Grünbaum and Motzkin proposed this theorem as a conjecture and proved the case r=2. David Larman  proved the case r=3.

roy

Roy Meshulam

Roy Meshulam and I studied a topological version of the theorem, namely you assume that every member of F is the union of at most r pairwise disjoint contractible compact sets in $R^d$ and that all these sets together form a good cover – every nonempty intersection is either empty or contractible. And we were able to prove it!

Eckhoff and Klaus Peter Nischke looked for a purely combinatorial version of Amenta’s theorem which is given by the old proofs (for r=2,3) but not by Amenta’s proof. An approach towards such a proof was already proposed by Morris in 1968, but it was not clear how to complete Morris’s work. Eckhoff and Nischke were able to do it! And this also implied the topological version for good covers.

The full results of Eckhoff and Nischke and of Roy and me are independent. Roy and I showed that if the nerve of \cal G is d-Leray then the nerve of \cal F is ((d+1)r-1)-Leray. Eckhoff and showed that if the nerve of \cal G has Helly number d, then the nerve of \cal F has Helly number (d+1)r-1. Amenta’s argument can be used to show that if the nerve of \cal G is d-collapsible then the nerve of F is  ((d+1)r-1)-collapsible.

Here, a simplicial comples K is d-Leray if all homology groups H_i(L) vanishes for every i \ge d and every induced subcomplex L of K.

Roy and I were thinking about a common homological generalization which will include both results but so far could not prove it.

 

And now let me move to the beginning:

1. 1981 – we give different proofs for the Perles-Katchalski Conjecture

Continue reading

Navier-Stokes Fluid Computers

how-magneto-rheological-suspension-works-8947_2

Smart fluid

Terry Tao posted a very intriguing post on the Navier-Stokes equation, based on a recently uploaded paper Finite time blowup for an averaged three-dimensional Navier-Stokes equation.

The paper proved a remarkable negative answer for the regularity conjecture for a certain variants of the NS equations, namely (or, perhaps, more precisely) the main theorem demonstrates finite time blowup for an averaged Navier-Stokes equation. (This already suffices to show that certain approaches for a positive answer to the real problem are not viable.) The introduction ends with the following words.

“This suggests an ambitious (but not obviously impossible) program (in both senses of
the word) to achieve the same e ffect for the true Navier-Stokes equations, thus obtaining a negative answer to Conjecture 1.1 (the regularity conjecture for 3D NS equation)… Somewhat analogously to how a quantum computer can be constructed from the laws of quantum mechanics [Here Tao links to Benio ff’s 1982 paper: “Quantum mechanical Hamiltonian models of Turing machines,”], or a Turing machine can be constructed from cellular automata such as “Conway’s Game of Life” , one could hope to design logic gates entirely out of ideal fluid (perhaps by using suitably shaped vortex sheets to simulate the various types of physical materials one would use in a mechanical computer). If these gates were sufficiently “Turing complete”, and also “noise-tolerant”, one could then hope to combine enough of these gates together to “program” a von Neumann machine consisting of ideal fluid that, when it runs, behaves qualitatively like the blowup solution used to establish Theorem 1.4.[The paper’s main theorem] Note that such replicators, as well as the related concept of a universal constructor, have been built within cellular automata such as the “Game of Life.”

Once enough logic gates of ideal fluid are constructed, it seems that the main difficulties in executing the above program are of a “software engineering” nature, and would be in principle achievable, even if the details could be extremely complicated in practice. The main mathematical difficulty in executing this “fluid computing” program would thus be to arrive at (and rigorously certify) a design for logical gates of inviscid fluid that has some good noise tolerance properties. In this regard, ideas from quantum computing (which faces a unitarity constraint somewhat analogous to the energy conservation constraint for ideal fluids, albeit with the key di fference of having a linear evolution rather than a nonlinear one) may prove to be useful. (Emphasis mine.)

Interesting idea!

And what Tao does go well beyond an idea, he essentially implement this program for a close relative of the NS equation!  I am not sure if universal computing is established for these systems but the proofs of the finite-time blow up theorem certainly uses some computational-looking gadget, and also as Terry explains some form of fault-tolerance.

Somewhat related ideas (unsupported by any results, of course,) appeared in the seventh post “Quantum repetition” of my debate with Aram Harrow on quantum computing.  (See, e.g., this remark, and this one, and this one.) The thread also contains interesting links, e.g. to Andy Yao’s paper “Classical physics and the Curch-Turing Thesis.”  In addition to the interesting question:

Does the NS-equation in three-dimension supports universal (classical) computation,

we can also ask what about two-dimensions?

Can NS-equations in two dimension be approximated in any scale by bounded depth circuits?

One general question suggested there was the following: “It can be of interest (and perhaps harder compared to the quantum case) to try to describe classical evolutions that do not enable/hide fault tolerance and (long) computation.”

Another interesting comment by Arie Israel is: “I was surprised to learn that experimental fluid mechanics people had thought of this analogy before. Apparently the key name is ‘Fluidics’ and those ideas date back at least to the sixties.”

cih2

Update: Here is the first paragraph from a nice article by  Erica Klarreich entitled A Fluid New Path in Grand Math Challenge on this development in Quanta Magazine:

In Dr. Seuss’s book “The Cat in the Hat Comes Back,” the Cat makes a stain he can’t clean up, so he calls upon the help of Little Cat A, a smaller, perfect replica of the Cat who has been hiding under the Cat’s hat. Little Cat A then calls forth Little Cat B, an even smaller replica hidden under Little Cat A’s hat. Each cat in turn lifts his hat to reveal a smaller cat who possesses all the energy and good cheer of the original Cat, just crammed into a tinier package. Finally, Little Cat Z, who is too small to see, unleashes a VOOM like a giant explosion of energy, and the stain disappears.

And here is a follow up post on Tao’s blog (and a few more II, III), and a post on Shtetl Optimized.

The flip side

Update (June 14): It is worth noting that while the purpose of Tao’s program is to show finite-time blow up of the 3D Navier Stokes equations (as is often the case) these lines of ideas can potentially be useful also toward a positive solution of the regularity conjectures. Specifically, one can try to show that 3D Navier-Stokes equations do not support universal classical computation and even more specifically do not support classical fault-tolerance and error correction. Also here some analogy with quantum computation can be useful: It is expected that for adiabatic processes computation requires “spectral gap” and that gapped evolutions with local Hamiltonians support only bounded depth computation. Something analogous may apply to NS equations in bounded dimensions.

There are many caveats, of course,  the quantum results are not proved for D>1, NS equations are non-linear which weakens the analogy, and showing that the evolution does not support computation does not imply, as far as we know, regularity.

Three more remarks: 1) On the technical level an important relevant technical tool for the results on gapped systems with local Hamiltonians is the Lieb-Robinson inequality. (See, e.g. this review paper.)  2) for classical evolutions a repetition mechanism (or the “majority function”) seems crucial for robust computation and it will be interesting specifically to test of 3D Navier-stokes support it; 3) If computation is not possible beyond bounded depth this fact may lead to additional conserved quantities for NS, beyond the classical ones. (One more, June 28): It looks to me that the crucial question is if NS equations only support bounded computation or not. So this distinction captures places where circuit complexity gives clear mathematical distinctions.

Amazing: Peter Keevash Constructed General Steiner Systems and Designs

KONICA MINOLTA DIGITAL CAMERA

Here is one of the central and oldest problems in combinatorics:

Problem: Can you find a collection S of q-subsets from an n-element set X set so that every r-subset of X is included in precisely λ sets in the collection?

A collection S  of this kind are called a design of parameters (n,q,r, λ),  a special interest is the case  λ=1, and in this case S is called a Steiner system.

For such an S to exist n should be admissible namely {{q-i} \choose {r-i}} should divide \lambda {{n-i} \choose {r-i}} for every 1 \le i \le r-1.

There are only few examples of designs when r>2. It was even boldly conjectured that for every q r and λ if n is sufficiently large than a design of parameters  (n,q,r, λ) exists but the known constructions came very very far from this.   … until last week. Last week, Peter Keevash gave a twenty minute talk at Oberwolfach where he announced the proof of the bold existence conjecture. Today his preprint the existence of designs, have become available on the arxive.

Brief history

The existence of designs and Steiner systems is one of the oldest and most important problems in combinatorics.

1837-1853 – The existence of designs and Steiner systems was asked by Plücker(1835), Kirkman (1846) and Steiner (1853).

1972-1975 – For r=2 which was of special interests, Rick Wilson proved their existence for large enough admissible values of n.

1985 -Rödl proved the existence of approximate objects (the property holds for (1-o(1)) r-subsets of X) , thus answering a conjecture by Erdös and Hanani.

1987  – Teirlink proved their existence for infinitely  many values of n when r and q are arbitrary and  λ is a certain large number depending on q and r but not on n. (His construction also does not have repeated blocks.)

2014 – Keevash’s  proved the existence of Steiner systems for all but finitely many admissible  values of n for every q and r. He uses a new method referred to as Randomised Algebraic Constructions.

Update: Just 2 weeks before Peter Keevash announced his result I mentioned the problem in my lecture in “Natifest” in a segment of the lecture devoted to the analysis of Nati’s dreams. 35:38-37:09.

Update: Some other blog post on this achievement: Van Vu Jordan Ellenberg, The aperiodical . A related post from Cameron’s blog Subsets and partitions.

Update: Danny Calegary pointed out a bird-eye similarity between Keevash’s strategy and the strategy of the  recent Kahn-Markovic proof of the Ehrenpreis conjecture http://arxiv.org/abs/1101.1330 , a strategy used again by Danny and Alden Walker to show that random groups contain fundamental groups of closed surfaces http://arxiv.org/abs/1304.2188 .

Many triangulated three-spheres!

The news

Eran Nevo and Stedman Wilson have constructed \exp (K n^2) triangulations with n vertices of the 3-dimensional sphere! This settled an old problem which stood open for several decades. Here is a link to their paper How many n-vertex triangulations does the 3 -sphere have?

Quick remarks:

1) Since the number of facets in an n-vertex triangulation of a 3-sphere is at most quadratic in n, an upper bound for the number of triangulations of the 3-sphere with n vertices is \exp(n^2 \log n). For certain classes of triangulations, Dey removed in 1992  the logarithmic factor in the exponent for the upper bound.

2) Goodman and Pollack showed in 1986 that the number of simplicial 4-polytopes with n vertices is much much smaller \exp (O(n\log n)). This upper bound applies to simplicial polytopes of every dimension d, and Alon extended it to general polytopes.

3) Before the new paper the world record was the 2004 lower bound by Pfeifle and Ziegler – \exp (Kn^{5/4}).

4) In 1988 I constructed \exp (K n^{[d/2]}) triangulations of the d-spheres with n vertices.  The new construction gives hope to improve it in any odd dimension by replacing [d/2] by [(d+1)/2] (which match up to logn the exponent in the upper bound). [Update (Dec 19) : this has now been achieved by Paco Santos (based on a different construction) and Nevo and Wilson (based on extensions of their 3-D constructions). More detailed to come.]

Polymath 8 – a Success!

mat2

Yitang Zhang

Update (July 22, ’14). The polymath8b paper “Variants of the Selberg sieve, and bounded intervals containing many primes“, is now on the arXiv. See also this post on Terry Tao’s blog. Since the last update, we also had here at HUJI a beautiful learning seminar on small gaps between primes. James Maynard gave a series of three lectures and additional lectures were given by Zeev Rudnick and Tamar Ziegler.

 

Update (Jan 9, ’14, corrected Jan 10):  Polymath8b have just led to an impressive progress: Goldston, Pintz, and Yıldırım showed that conditioned on the  Elliott-Halberstam conjecture (EHC) there are infinitely many primes of bounded gap below 16. Maynard improved it to 12. Polymath8b have just improved it based on a generalized form of the EHC (proposed in 1986 by Bombieri, Friedlander, and  Iwaniec) further to 8.  [Further update:  6 and there are reasons so suspect that further improvement requires major breakthrough – namely getting over the “parity problem”.] The unconditional bound for gaps stands now on 270.

Update: A paper by James Maynard entitled “Small gaps between primes” proved that for  every k there are infinitely many intervals of length f(k) each containing at least k primes. He also reduced the gap between infinitely many pairs of primes to 600. The method is also (said to be) much simpler. Amazing! Similar results were obtained independently by Terry Tao.

Terry Tao launched a followup polymath8b to  improve the bounds for gaps between primes based on Maynard’s results.

Update: Here is the paper: A NEW BOUND FOR GAPS BETWEEN PRIMES by D. H. J. Polymath.

Zhang’s breakthrough and Polymath8

The main objectives of the polymath8 project, initiated by Terry Tao back in June, were “to understand the recent breakthrough paper of Yitang Zhang establishing an infinite number of prime gaps bounded by a fixed constant {H}, and then to lower that value of {H} as much as possible.”

Polymath8 was a remarkable success! Within two months the best value of H that was 70,000,000 in Zhang’s proof was reduced to 5,414. Moreover, the polymath setting looked advantageous for this project, compared to traditional ways of doing mathematics.

The polymath project gave opportunity to a number of researchers to understand Zhang’s proof and the earlier breakthrough by Daniel Goldston, János Pintz, and Cem Yıldırım. It also gave an opportunity to a larger number of mathematicians to get some feeling about the involved mathematics.

The story

Twin primes are two primes p and p+2. The ancient twin prime conjecture asserts that there are infinitely many twin primes. The prime number theorem asserts that there are (asymptotically)  n/log n primes whose value is smaller than a positive integer n, and this implies that we can find arbitrary large pairs of consecutive primes  p and q such that q-p is at most (log p). Until a few years ago nothing asymptotically better was known. Goldston, Pintz, and Yıldırım (GPY), showed in 2005 that there infinitely many pairs of primes p and q such that q-p is O(\sqrt {\log n}). A crucial idea was to derive information on gaps of primes from the distribution of primes in arithmetic progressions. GPY showed that conditioned on the  Elliott-Halberstam conjecture (EHC) there are infinitely many primes of bounded gaps (going all the way to 16, depending on a certain parameter in the conjecture, but not to 2). Yitang Zhang did not prove the EHC but based on further understanding of the situation found a way to shortcut the conjecture and to prove that there are infinitely many primes of with bounded gaps unconditionally!

Here is a very nice 2007 survey article by Kannan Soundararajan on this  general area of research and the GPY breakthrough. (One thing I recently learned is that  Soundararajan is called by friends and colleagues “Sound”. ) This article starts with a very thoughtful and endearing answer to the quastion: “Why do we care at all? After all primes were meant to be multiplied, not subtracted (or added).”

Here is a short list of thoughts (things I learned, things I wish to understand better…) from following (from distance) Polymath8 and related Internet activity.

1) How information on primes in arithmetic progressions leads to information on gaps between primes?

I do not really understand why the information on primes in arithmetic progressions e.g. the Elliott-Halberstam conjecture lead to the conclusion regarding primes with bounded gaps. I would be very happy to get a feeling for it.

2) The three-primes barrier.

Already GPY  tried to extend their methods to show the existence of three primes in a bounded interval of integers. So far, it is not known how to show that intervals of the form [n,n+o(log n)] contain triples of primes infinitely often. Perhaps, to actually solve the twin prime conjecture we will need to get a breakthrough for triples of primes, but maybe not. See also this MO question asked by Noam Elkies.

Update: Here is another interesting MO question Quantitative lower bounds related to Zhang’s theorem on bounded gaps, asked by Eric Naslund. Eric asks: what can be say based on Zhang’s work about the smallest value  of a pair of primes of distance k apart?

3) Cauchy-Schwarz everywhere;

This may sound silly but the way Cauchy-Schwarz (C-S) inequality is used again and again make you wonder again why C-S is it so useful, and why it is mainly C-S which is so useful.

4) Can detailed statistical understanding of primes in sets other than AP  be useful?

In recent years there was much activity (and I also was interested) in Mobius randomness and analogs of the prime number theorem for various more complicated subsets of integers. (E.g., subsets defined by various properties of the digital expansion.) Can understanding of this kind  also be used for the prime-gaps questions?

5) Usefulness of Deligne’s work on Riemann’s hypothesis for functions fields for questions in analytic number theory.

I knew, of course that Deligne famously proved analogs of the Riemann hypothesis for function fields in great generality but I was not aware that these results have applications to “ordinary” analytic number theory. Again, this is something I would be happy to know a little more about. There is a nice recent post on the Riemann hypothesis in various settings on “What’s new”.

6) Parity problem.  (Added Nov 27) There is a difficult “parity problem” which seems to be a difficult obstacle for getting the gap to two. (And for various related goals). Terry Tao wrote about it in 2007 in this post. In polymath8b VII an attempt to cross the “parity barrier” was  made but (as people expected) it turned out that the parity barrier indeed shows up causes this attempt to fail. (Update July 14:) This is further explained in this new post over Tao’s blog.

7) (Added Nov 27) One thing I am curious about is the following. Consider a random subset of primes (taking every prime with probability p, independently, and say p=1/2). Now consider only integers involving these primes. I think that it is known that this system of “integers” satisfies (almost surely) PNT but not at all RH. We can consider the properties BV (Bombieri Vinogradov), or more generally EH(θ) and the quantities H_m. For such systems does BV typically hold? or it is rare like RH. Is Meynard’s implication applies in this generality? Nicely here we can hope even for infinite consecutive primes. Update: after thinking about it further and a little discussion over polymath8b it looks that current sieve methods, and some of the involved statements, rely very strongly on both the multiplicative and additive structure of the integers and do not allow extensions to other systems of “integers.”

 

 

Update (August 23): Before moving to small gaps, Sound’s 2007 survey briefly describes the situation for large gaps. The Cramer probabilistic heuristic suggests that there are consecutive primes in [1,n] which are c(\log n)^2 apart, but not C (\log n)^2 apart where c and C are some small and large positive constants.  It follows from the prime number theorem that there is a gap of at least \log n. And there were a few improvements in the 30s ending with a remarkable result by Rankin who showed that there is a gap as large as \log n times \log \log n \log \log \log \log n (log log log n)^{-2}. Last week Kevin Ford, Ben Green, Sergei Konyagin, and Terry Tao and independently James Maynard were able to  improve Rankin’s estimate by a function that goes to infinity with n.  See this post on “What’s new.”

 

Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture

Borsuk asked in 1933 if every bounded set K of diameter 1 in R^d can be covered by d+1 sets of smaller diameter. A positive answer was referred to as the “Borsuk Conjecture,” and it was disproved by Jeff Kahn and me in 1993. Many interesting open problems remain.  The first two posts in the series “Around Borsuk’s Conjecture” are here and here. See also these posts (I,II,III, IV), and the post “Surprises in mathematics and theory” on Lipton and Reagan’s blog GLL.

Can we save the conjecture? We can certainly try, and in this post I would like to examine the possibility that Borsuk’s conjecture is correct except from some “coincidental” sets. The question is how to properly define “coincidental.”

Let K be a set of points in R^d and let A be a set of pairs of points in K. We say that the pair (K, A) is general if for every continuous deformation of the distances on A there is a deformation K’ of K which realizes the deformed distances.

(This condition is related to the “strong Arnold property” (aka “transversality”) in the theory of Colin de Verdière invariants of graphs; see also this paper  by van der Holst, Lovasz and Schrijver.)

Conjecture 1: If D is the set of diameters in K and (K,D) is general then K can be partitioned into d+1 sets of smaller diameter.

We propose also (somewhat stronger) that this conjecture holds even when “continuous deformation” is replaced with “infinitesimal deformation”.

The finite case is of special interest:

A graph embedded in R^d is stress-free if we cannot assign non-trivial weights to the edges so that the weighted sum of the edges containing any  vertex v (regarded as vectors from v) is zero for every vertex v. (Here we embed the vertices and regard the edges as straight line segments. (Edges may intersect.) Such a graph is called a “geometric graph”.) When we restrict Conjecture 1 to finite configurations of points we get.

Conjecture 2: If G is a stress free geometric graph of diameters in R^d  then G is (d+1)-colorable.

A geometric graph of diameters is a geometric graph with all edges having the same length and all non edged having smaller lengths. The attempt for “saving” the Borsuk Conjecture presented here and Conjectures 1 and 2 first appeared in a 2002 collection of open problems dedicated to Daniel J. Kleitman, edited by Douglas West.

When we consider finite configurations of points  we can make a similar conjecture for the minimal distances:

Conjecture 3: If the geometric graph of pairs of vertices realizing the minimal distances of a point-configuration in R^d is stress-free, then it is (d+1)-colorable.

We can speculate that even the following stronger conjectures are true:

Conjecture 4: If G is a stress-free geometric graph in R^d so that all edges in G are longer than all non-edges of G, then G is (d+1)-colorable.

Conjecture 5: If G is a stress-free geometric graph in R^d so that all edges in G are shorter than all non-edges of G, then G is (d+1)-colorable.

We can even try to extend the condition further so edges in the geometric graph will be larger (or smaller) than non-edges only just “locally” for neighbors of each given vertex.

Comments:

1) It is not true that every stress-free geometric graph in R^d is (d+1)-colorable, and not even that every stress-free unit-distance graph is (d+1)-colorable. Here is the (well-known) example referred to as the Moser Spindle. Finding conditions under which stress-free graphs in R^d are (d+1)-colorable is an interesting challenge.

MoserSpindle_700

2) Since a stress-free graph with n vertices has at most dn - {{d+1} \choose {2}} edges it must have a vertex of degree 2d-1 or less and hence it is 2d colorable. I expect this to be best possible but I am not sure about it. This shows that our “saved” version of Borsuk’s conjecture is of very different nature from the original one. For graphs of diameters in R^d the chromatic number can, by the work of Jeff and me be exponential in \sqrt d.

3) It would be interesting to show that conjecture 1 holds in the non-discrete case when  d+1 is replaced by 2d.

4) Coloring vertices of geometric graphs where the edged correspond to the minimal distance is related also the the well known Erdos-Faber-Lovasz conjecture.ERDSFA~1.

See also this 1994 article by Jeff Kahn on Hypergraphs matching, covering and coloring problems.

5) The most famous conjecture regarding coloring of graphs is, of course, the four-color conjecture asserting that every planar graph is 4-colorable that was proved by Appel and Haken in 1976.  Thinking about the four-color conjecture is always both fascinating and frustrating. An embedding for maximal planar graphs as vertices of a convex 3-dimensional polytope is stress-free (and so is, therefore, also a generic embedding), but we know that this property alone does not suffice for 4-colorability. Finding further conditions for  stress-free graphs in R^d that guarantee (d+1)-colorability can be relevant to the 4CT.

An old conjecture of mine asserts that

Conjecture 6: Let G be a graph obtained from the graph of a d-polytope P by triangulating each (non-triangular) face with non-intersecting diagonals. If G is stress-free (in which case the polytope P is called “elementary”) then G is (d+1)-colorable.

Closer to the conjectures of this post we can ask:

Conjecture 7: If G is a stress-free geometric graph in R^d so that for every edge  e of G  is tangent to the unit ball and every non edge of G intersect the interior of the unit ball, then G is (d+1)-colorable.

A question that I forgot to include in part I.

What is the minimum diameter d_n such that the unit ball in R^n can be covered by n+1 sets of smaller diameter? It is known that 2-C'\log n/n \le d_n\le 2-C/n for some constants C and C’.

Poznań: Random Structures and Algorithms 2013

michal  photo

Michal Karonski (left) who built Poland’s probabilistic combinatorics group at Poznań, and a sculpture honoring the Polish mathematicians who first broke the Enigma machine (right, with David Conlon, picture taken by Jacob Fox).

I am visiting now Poznań for the 16th Conference on Random Structures and Algorithms. This bi-annually series of conferences started 30 years ago (as a satellite conference to the 1983 ICM which took place in Warsaw) and this time there was also a special celebration for Bela Bollobás 70th birthday. I was looking forward to  this first visit to Poland which is, of course, a moving experience for me. Before Poznań I spent a few days in Gdańsk visiting Robert Alicki. Today (Wednesday)  at the Poznań conference I gave a lecture on threshold phenomena and here are the slides. In the afternoon we had the traditional random run with a record number of runners. Let me briefly tell you about very few of the other lectures: Update (Thursday): A very good day, and among others a great talk of Jacob Fox on Relative Szemeredi Theorem (click for the slides from a similar talk from Budapest) where he presented a joint work with David Conlon and Yufei Zhao giving a very general and strong form of Szemeredi theorem for quasi-random sparse sets, which among other applications, leads to a much simpler proof of the Green -Tao theorem.

Mathias Schacht

Mathias Schacht gave a wonderful talk  on extremal results in random graphs (click for the slides) which describes some large recent body of highly successful research on the topic. Here are two crucial slides, and going through the whole presentation can give a very good overall picture. ms1 mt2

Vera Sós

Vera Sós gave an inspiring talk about the random nature of graphs which are extremal to the Ramsey property and connections with graph limits. Vera presented the following very interesting conjecture on graph limits. We say that a sequence of graphs (G_n) has a limit if for every k and every graph H with k vertices the proportion in G_n of induced H-subgraphs among all k-vertex induced subgraphs tend to a limit. Let us also say that (G_n) has a V-limit if for every k and every e the proportion in G_n of induced subgraphs with k vertices and e edges among all k-vertex induced subgraphs tend to a limit. Sós’ question: Is having a V-limit equivalent to having a limit. This is open even in the case of quasirandomness, namely, when the limit is given by the Erdos-Renyi model G(n,p). (Update: in this case V-limit is equivalent to limit, as several participants of the conference observed.) Both a positive and a negative answer to this fundamental question would lead to many further (different) open problems.

Joel Spencer

Joel Spencer gave a great (blackboard) talk about algorithmic aspects of the probabilistic method, and how existence theorems via the probabilistic method now often require complicated randomized algorithm. Joel mentioned his famous six standard deviation theorem. In this case, Joel conjectured thirty years ago that there is no efficient algorithm to find the coloring promised by his theorem. Joel was delighted to see his conjecture being refuted first by Nikhil Bansal (who found an algorithm whose proof depends on the theorem) and then later by Shachar Lovett and  Raghu Meka (who found a new algorithm giving a new proof) . In fact, Joel said, having his conjecture disproved is even more delightful than having it proved. Based on this experience Joel and I are now proposing another conjecture: Kalai-Spencer (pre)conjecture: Every existence statement proved by the probabilistic method can be complemented by an efficient (possibly randomized) algorithm. By “complemented by an efficient algorithm” we mean that there is an efficient(polynomial time)  randomized algorithm to create the promised object with high probability.  We refer to it as a preconjecture since the term “the probabilistic method” is not entirely well-defined. But it may be possible to put this conjecture on formal grounds, and to discuss it informally even before.

Some old and new problems in combinatorics and geometry

Paul99

Paul Erdős in Jerusalem, 1933  1993

I just came back from a great Erdős Centennial conference in wonderful Budapest. I gave a lecture on old and new problems (mainly) in combinatorics and geometry (here are the slides), where I presented twenty problems, here they are:

Around Borsuk’s Problem

Let f(d) be the smallest integer so that every set of diameter one in R^d can be covered by f(d) sets of smaller diameter. Borsuk conjectured that f(d) \le d+1.

It is known (Kahn and Kalai, 1993) that : f(d) \ge 1.2^{\sqrt d}and also that (Schramm, 1989) f(d) \le (\sqrt{3/2}+o(1))^d.

Problem 1: Is f(d) exponential in d?

Problem 2: What is the smallest dimension for which Borsuk’s conjecture is false?

Volume of sets of constant width in high dimensions

Problem 3: Let us denote the volume of the n-ball of radius 1/2 by V_n.

Question (Oded Schramm): Is there some \epsilon >0 so that for every n>1 there exist a set K_n of constant width 1 in dimension n whose volume satisfies VOL(K_n) \le (1-\epsilon)^n V_n.

Around Tverberg’s theorem

Tverberg’s Theorem states the following: Let x_1,x_2,\dots, x_m be points in R^d with m \ge (r-1)(d+1)+1Then there is a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that  \cap _{j=1}^rconv (x_i: i \in S_j) \ne \emptyset.

Problem 4:  Let t(d,r,k) be the smallest integer such that given m points  x_1,x_2,\dots, x_m in R^d, m \ge t(d,r,k) there exists a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that every k among the convex hulls conv (x_i: i \in S_j), j=1,2,\dots,r  have a point in common.

Reay’s “relaxed Tverberg conjecture” asserts that that whenever k >1 (and k \le r), t(d,r,k)= (d+1)(r-1)+1.

Problem 5: For a set A, denote by T_r(A) those points in R^d which belong to the convex hull of r pairwise disjoint subsets of X. We call these points Tverberg points of order r.

Conjecture: For every A \subset R^d , \sum_{r=1}^{|A|} {\rm dim} T_r(A) \ge 0.

Note that \dim \emptyset = -1.

Problem 6:   How many points T(d;s,t) in R^d guarantee that they can be divided into two parts so that every union of s convex sets containing the first part has a non empty intersection with every union of t convex sets containing the second part.

A question about directed graphs

Problem 7: Let G be a directed graph with n vertices and 2n-2 edges. When can you divide your set of edges into two trees T_1 and T_2 (so far we disregard the orientation of edges,) so that when you reverse the directions of all edges in T_2 you get a strongly connected digraph.

Erdős-Ko-Rado theorem meets Catalan

Problem 8 

Conjecture: Let \cal C be a collection of triangulations of an n-gon so that every two triangulations in \cal C share a diagonal.  Then |{\cal C}| is at most the number of triangulations of an (n-1)-gon.

F ≤ 4E

Problem 9: Let K be a two-dimensional simplicial complex and suppose that K can be embedded in R^4. Denote by E the number of edges of K and by F the number of 2-faces of K.

Conjecture:  4E

A weaker version which is also widely open and very interesting is: For some absolute constant C C E.

Polynomial Hirsch

Problem 10:  The diameter of graphs of d-polytopes with n facets is bounded above by a polynomial in d and n.

Analysis – Fixed points

Problem 11: Let K be a convex body in R^d. (Say, a ball, say a cube…) For which classes \cal C of functions, every f \in {\cal C} which takes K into itself admits a fixed point in K.

Number theory – infinitely many primes in sparse sets

Problem 12: Find a (not extremely artificial) set A of integers so that for every n, |A\cap [n]| \le n^{0.499}where you can prove that A contains infinitely many primes.

Möbius randomness for sparse sets

Problem 13: Find a (not extremely artificial) set A of integers so that for every n, |A\cap [n]| \le n^{0.499} where you can prove that

\sum \{\mu(k): k \le n, k \in A\} = o(|A \cap [n]).

Computation – noisy game of life

Problem 14: Does a noisy version of Conway’s game of life support universal computation?

Ramsey for polytopes

Problem 15: 

Conjecture: For a fixed k, every d-polytope of sufficiently high dimension contains a k-face which is either a simplex or a (combinatorial) cube.

Expectation thresholds and thresholds

Problem 16: Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H’ in G in G(n,q) is at least 1/2 for every subgraph H’ of H. Let p be the value for which the probability that G in G(n,p) contains a copy of H is 1/2.

Conjecture: [Kahn – Kalai 2006]  p/q = O( log n)

Traces

Problem 17: Let X be a family of subsets of [n]=\{1,2,\dots,n\}.
How large X is needed to be so that the restriction (trace) of X to some set B \subset [n]|B|=(1/2+\delta)n has at least 3/4 \cdot 2^{|B|} elements?

Graph-codes

Problem 18: Let  P  be a property of graphs. Let \cal G be a collection of graphs with n vertices so that the symmetric difference of two graphs in \cal G has property PHow large can \cal G be.

Conditions for colorability

Problem 19: A conjecture by Roy Meshulam and me:

There is a constant C such that every graph G
with no induced cycles of order divisible by 3 is colorable by C colors.

Problem 20:

Another conjecture by Roy Meshulam and me: For every b>0 there
is a constant C=C(b) with the following property:

Let G be a graph such that for all its induced subgraphs H

The number of independent sets of odd size minus the number of independent sets of even size is between -b  and b.

Then G is colorable by C(b) colors.

Remarks:

The title of the lecture is borrowed from several papers and talks by Erdős. Continue reading