Category Archives: Open problems

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

Update: Here is a link to a draft of a paper* based on the first part of this lecture. Some old and new problems in combinatorial geometry I: Around Borsuk’s problem.

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

Andriy Bondarenko Showed that Borsuk’s Conjecture is False for Dimensions Greater Than 65!

The news in brief

Andriy V. Bondarenko proved in his remarkable paper The Borsuk Conjecture for two-distance sets  that the Borsuk’s conjecture is false for all dimensions greater than 65. This is a substantial improvement of the earlier record (all dimensions above 298) by Aicke Hinrichs and Christian Richter.

Borsuk’s conjecture

Borsuk’s conjecture asserted that every set of diameter 1 in d-dimensional Euclidean space can be covered by d+1 sets of smaller diameter. (Here are links to a post describing the disproof by Kahn and me  and a post devoted to problems around Borsuk’s conjecture.)

Two questions posed by David Larman

David Larman posed in the ’70s two basic questions about Borsuk’s conjecture:

1) Does the conjecture hold for collections of 0-1 vectors (of constant weight)?

2) Does the conjecture hold for 2-distance sets? 2-distance sets are sets of points such that the pairwise distances between any two of them have only two values.

Reducing the dimensions for which Borsuk’s conjecture fails

In 1993 Jeff Kahn and I disproved Borsuk’s conjecture in dimension 1325 and all dimensions greater than 2014. Larman’s first conjecture played a special role in our work.   While being a special case of Borsuk’s conjecture, it looked much less correct.

The lowest dimension for a counterexample were gradually reduced to  946 by A. Nilli, 561 by A. Raigorodskii, 560 by  Weißbach, 323 by A. Hinrichs and 320 by I. Pikhurko. Currently the best known result is that Borsuk’s conjecture is false for n ≥ 298; The two last papers relies strongly on the Leech lattice.

Bondarenko proved that the Borsuk’s conjecture is false for all dimensions greater than 65.  For this he disproved Larman’s second conjecture.

Bondarenko’s abstract

In this paper we answer Larman’s question on Borsuk’s conjecture for two-distance sets. We found a two-distance set consisting of 416 points on the unit sphere in the dimension 65 which cannot be partitioned into 83 parts of smaller diameter. This also reduces the smallest dimension in which Borsuk’s conjecture is known to be false. Other examples of two-distance sets with large Borsuk’s numbers will be given.

Two-distance sets

There was much interest in understanding sets of points in R^n  which have only two pairwise distances (or K pairwise distances). Larman, Rogers and Seidel proved that the maximum number can be at most (n+1)(n+4)/2 and Aart Blokhuis improved the bound to (n+1)(n+2)/2. The set of all 0-1 vectors of length n+1 with two ones gives an example with n(n+1)/2 vectors.

Equiangular lines

This is a good opportunity to mention another question related to two-distance sets. Suppose that you have a set of lines through the origin in R^n so that the angles between any two of them is the same. Such  a set is  called an equiangular set of lines. Given such a set of cardinality m, if we take on each line one unit vector, this gives us a 2-distance set. It is known that m ≤ n(n+1)/2 but for a long time it was unknown if a quadratic set of equiangular lines exists in high dimensions. An exciting breakthrough came in 2000 when Dom deCaen constructed a set of equiangular lines in R^n with 2/9(n+1)^2 lines for infinitely many values of n.

Strongly regular graphs

Strongly regular graphs are central in the new examples. A graph is strongly regular if every vertex has k neighbors, every adjacent pair of vertices have λ common neighbors and every non-adjacent pair of vertices have μ common neighbors. The study of strongly regular graphs (and other notions of strong regularity/symmetry) is a very important area in graph theory which involves deep algebra and geometry. Andriy’s construction is based on a known strongly regular graph G_2(4).

New Ramanujan Graphs!

margulis1

margulis2

Margulis’ paper

Ramanujan graphs were constructed independently by Margulis and by Lubotzky, Philips and Sarnak (who also coined the name). The picture above shows Margulis’ paper where the graphs are defined and their girth is studied. (I will come back to the question about girth at the end of the post.) In a subsequent paper Margulis used the girth property in order to construct efficient error-correcting codes. (Later Sipser and Spielman realized how to use the expansion property for this purpose.)

The purpose of this post is to briefly tell you about new Ramanujan graphs exhibited by Adam Marcus, Daniel Spielman, and Nikhil Srivastava. Here is the paper. This construction is remarkable for several reasons: First, it is the first elementary proof for the existence of Ramanujan graphs which also shows, for the first time, that there are k-regular Ramanujan graphs (with many vertices)  when k is not q+1, and q is a prime power. Second, the construction uses a novel “greedy”-method (with further promised fruits) based on identifying classes of polynomials with interlacing real roots, that does not lead (so far) to an algorithm (neither deterministic nor randomized). Third, the construction relies on Nati Linial’s idea of random graph liftings and verify (a special case of) a beautiful conjecture of Yonatan Bilu and Linial.  Continue reading

F ≤ 4E

1. E ≤ 3V

Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that

3V

In fact, we have (when V is at least 3,) that E 3V – 6.

To see this,  denote by F the number of regions or faces determined by G (in other words, the number of connected components in the complement of the embedded graph). Euler’s theorem asserts that

E – V + F = 2

V – E + F = 2

and now note that every face must have at least three edges and every edge is contained in two faces and therefore 2E \ge 3F, so 6=3V – 3E + 3F ≤ 3V – 3E +2E.

2. F  4E

Now 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.

Here is a really great conjecture:

Conjecture:

4E

A weaker version which is also widely open and very interesting is:

For some absolute constant C,

C E

Remarks: The conjecture extends to higher dimensions. If K is an r-dimensional simplicial complex that can be embedded into R^{2r} then the conjecture is that

f_r(K) \le C_rf_{r-1}(K),

Where C_r is a constant depending on r.  Here f_i(K) is the number of i-dimensional faces of K. A stronger statement is that C_r= r+2. The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ’embed’ refers to a topological embedding.