# Analysis of Boolean functions – week 2

### Post on week 1; home page of the course analysis of Boolean functions

Lecture II:

We discussed two important examples that were introduced by Ben-Or and Linial: Recursive majority and  tribes.

Recursive majority (RM): $F_m$ is a Boolean function with $3^m$ variables and $F_{m+1} (x,y,z) = F_1(F_m(x),F_m(y),F_m(z))$. For the base case we use the majority function $F_1(x,y,z)=MAJ(x,y,z)$.

Tribes: Divide your n variables into s pairwise disjoint sets (“tribes”) of cardinality t. f=1 if for some tribe all variables equal one, and thus T=0 if for every tribe there is a variable with value ‘0’.

We note that this is not an odd function i.e. it is not symmetric with respect to switching ‘0’ and ‘1’. To have $\mu=1/2$ we need to set $t=\log_2n - \log_2\log_2n+c$. We computed the influence of every variable to be C log n/n. The tribe function is a depth-two formula of linear size and we briefly discussed what are Boolean formulas and Boolean circuits (These notions can be found in many places and also in this post.).

I states several conjectures and questions that Ben-Or and Linial raised in their 85 paper:

Conjecture 1: For every balanced Boolean function with n variables there is a variable k whose influence is $\Omega (\log n/n)$.

Conjecture 2: For every balanced Boolean function with n variables there is a set S of n/log n variables whose influence $I_S(f)$ is 1-o(1).

Question 3: To what extent can the bound in Conjecture 2 be improved if the function f is odd. (Namely, $f(1-x_1,1-x_2,\dots, 1-x_n)=1-f(x_1,x_2,\dots, x_n)$.)

Our next theme was discrete isoperimetric results.  I noted the connection between total influence and edge expansion and proved the basic isoperimetric inequality: If μ(f)=t then I(f) ≥ 4 t(1-t). The proof uses the canonical paths argument.

### Lecture III:

We proved using “compression” that sharp bound on I(f) as a function of t=μ(f). We made the analogy between compression and Steiner symmetrization – a classic method for proving the classical isoperimetric theorem. We discussed similar results on vertex boundary and on Talagrand-Margulis boundary (to be elaborated later in the course).

Then We proved the Harris-Kleitman inequality and showed how to deduce the fact that intersecting family of subsets of [n] with the property that the family of complements is also intersecting has at most $2^{n-2}$ sets.

The next topic is spectral graph theory. We proved the Hoffman bound for the largest size of an independent set in a graph G.

I mentioned graph-Laplacians and the spectral bound for expansions (Alon-Milman, Tanner)..

The proofs mentioned above are so lovely that I will add them on this page, but sometime later.

Next week I will introduce harmonic analysis on the discrete cube and give a Fourier-theoretic explanation for  the additional log (1/t) factor in the edge isoperimetric inequality.

Important announcement: Real analysis boot camp in the Simons Institute for the Theory of Computing, is part of the program in Real Analysis and Computer Science. It is taking place next week on September 9-13 and has three lecture series. All lecture series are related to the topic of the course and especially:

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

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.

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

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

# Analysis of Boolean Functions – week 1

In the first lecture I defined the discrete n-dimensional cube and  Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets.

1) The largest possible intersecting family of subsets of [n];

2) The largest possible intersecting family of subsets of [n] so that the family of complements is also intersecting;

3) The largest possible family of graphs on v vertices such that each two graphs in the family contains a common triangle;

4) Chvatal’s conjecture regarding the maximum size of an intersecting family of sets contained in an ideal of sets;

Exercise: Prove one of the following

a) The Harris-Kleitman’s inequality

b) (from the H-K inequality) Every family of subsets of [n] with the property that every two sets have non-empty intersection and no full union contains at most $2^{n-2}$ sets.

More reading: this post :”Extremal combinatorics I: extremal problems on set systems“. Spoiler: The formulation of Chvatal’s conjecture but also the answer to the second exercise can be found on this post: Extremal combinatorics III: some basic theorems. (See also peoblen 25 in the 1972 paper Selected combinatorial research problems by Chvatal, Klarner and Knuth.)

I moved to discuss the problem of collective coin flipping and the notion of influence as defined by Ben-Or and Linial. I mentioned the Baton-passing protocol, the Alon-Naor result, and Feige’s two-rooms protocol.

More reading: this post :” Nati’s influence“. The original paper of Ben-Or Linial:  Collective coin flipping, M. Ben-Or  and N. Linial, in “Randomness and    Computation” (S. Micali ed.) Academic Press, New York, 1989, pp.    91-115.

# Poznań: Random Structures and Algorithms 2013

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.

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

# Lawler-Kozdron-Richards-Stroock’s combined Proof for the Matrix-Tree theorem and Wilson’s Theorem

David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics”

A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchho ff and Wilson via Kozdron and Stroock. The lecture is based on the work presented in the very recent paper by Michael J. Kozdron,  Larissa M. Richards, and Daniel W. Stroock: Determinants, their applications to Markov processes, and a random walk proof of Kirchhoff’s matrix tree theorem. Preprint, 2013. Available online at arXiv:1306.2059.

Here is the abstract:

Kirchhoff’s formula for the number of spanning trees in a connected graph  is over 150 years old. For example, it says that if $c_2, \dots, c_n$ are the nonzero  eigenvalues of the Laplacian, then the number k of spanning trees is $k= (1/n)c_2\cdots c_n.$ There are many proofs.  An algorithm due to Wilson via loop erased random walks produces such a tree, and Wilson’s theorem is that all spanning trees are produced by his algorithm with equal probability. Hence,  after the fact, we know that Wilson’s algorithm produces any given tree with probability 1/k.  A proof due to Lawler, using the Green’s function, shows directly that Wilson’s algorithm has the probability 1/k  of producing any given spanning tree, thus simultaneously proving Wilson’s theorem and Kirchhoff’s formula. Lawler’s proof has been considerably simplified by Kozdron and Stroock. I plan to explain their proof. The lecture will be completely self-contained, using only Cramer’s rule from linear algebra.

(Here are also lecture notes of the lecture by Ron Rosenthal.)

Here is some background.

## The matrix-tree theorem

The matrix tree theorem asserts that the number of rooted spanning trees of a connected graph G  is the product of the non-zero eigenvalues of L(G), the Laplacian of G.

Suppose that G has n vertices. The Laplacian of G is the matrix whose (i,i)-entry is the degree of the ith vertex, and its (i,j) entry for $i \ne j$ is 0 if the ith vertex is not adjacent to the jth vertex, and -1 if they are adjacent. So  L(G)=D-A(G) where A(G) is the adjacency matrix of G, and D is a diagonal matrix whose entries are the degrees of the vertices.  An equivalent formulation of the matrix-tree theorem is that the number of spanning trees is the determinant of a matrix obtained from the Laplacian by deleting the j th row and j th column.

We considered a high dimensional generalization of the matrix tree theorem in these posts (I, II, III, IV).

## How to generate a random spanning tree for a graph G?

### Using the matrix-tree theorem

Method A: Start with an edge $e \in G$, use the matrix-tree theorem to compute the probability $p_e$ that e belongs to a random spanning tree of G, take e with probability $p_e$. If e is taken consider the contraction $G/e$ and if G is not taken consider the deletion $G \backslash e$ and continue.

This is an efficient method to generate a random spanning tree according to the uniform probability distribution. You can extend it by assigning each edge a weight and chosing a tree with probability proportional to the product of its weights.

### Random weights and greedy

Method B: Assign each edge a random real number between 0 and 1 and chose the spanning tree which minimizes the sum of weights via the greedy algorithm.

This is a wonderful method but it leads to a different probability distribution on random spanning trees which is very interesting!

### The Aldous-Broder random walk method

Method C: The Aldous-Broder theorem. Start a simple random walk from a vertex of the graph until reaching all vertices, and take each edge that did not form a cycle with earlier edges. (Or, in other words, take every edge that reduced the number of connected components of the graph on the whole vertex set and visited edges.)

Amazingly, this leads to a random uniform spanning tree. The next method is also very amazing and important for many applications.

### David Wilson’s algorithm

Method D: Wilson’s algorithm. Fix a vertex as a root. (Later the root will be a whole set of vertices, and a tree on them.) Start from an arbitrary vertex u not in the root and take a simple random walk until you reach the root. Next, erase all edges in cycles of the path created by the random walk so you will left with a simple path from  u to the root. Add this path to the root and continue!

Here is a link to Wilson’s paper! Here is a nice presentation by Chatterji  and Gulwani.

# Some old and new problems in combinatorics and geometry

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)+1$Then 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.

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!

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

# Andrei

Andrei Zelevinsky passed away a week ago on April 10, 2013, shortly after turning sixty. Andrei was a great mathematician and a great person. I first met him in a combinatorics conference in Stockholm 1989. This was the first major conference in combinatorics (and perhaps in all of mathematics) with massive participation of mathematicians from the Soviet Union, and it was a meeting point for east and west and for different areas of combinatorics. The conference was organized by Anders Björner who told me that Andrei played an essential role helping to get the Russians to come. One anecdote I remember from the conference was that Isreal Gelfand asked Anders to compare the quality of his English with that of Andrei. “Isreal”, told him Anders politely, “your English is very good, but I must say that Andrei’s English is a touch better.” Gelfand was left speechless for a minute and then asked again: “But then, how is my English compared with Vera’s?” In 1993, Andrei participated in a combinatorics conference that I organized in Jerusalem (see pictures below), and we met on various occasions since then. Andrei wrote a popular blog (mainly) in Russian Avzel’s journal. Beeing referred there once as an “esteemed colleague” (высокочтимым коллегой) and another time as  “Gilushka” demonstrates the width of our relationship.

Let me mention three things from Andrei’s mathematical work.

Andrei is famous for the Bernstein-Zelevinsky theory. Bernstein and Zelevinsky classified the irreducible complex representations of a general linear group over a local field in terms of cuspidal representations. The case of GL(2) was carried out in the famous book by Jacquet-Langlands, and the theory for GL(n) and all reductive groups was a major advance in representation theory.

The second thing I would like to mention is Andrei’s work with Gelfand and Kapranov on genaralized hypergeometric functions. To get some impression on the GKZ theory you may look at the BAMS’ book review of their book written by Fabrizio Catanese. This work is closely related to the study of toric varieties, and it introduced the secondary polytopes. The secondary polytopes is a polytope whose vertices correspond to (certain) triangulations of a polytope P. When P is a polygon then the secondary polytope is the associahedron (also known as the Stasheff polytope).

The third topic is  the amazing cluster algebras.  Andrei Zelevinsky and Sergey Fomin invented cluster algebras which turned out to be an extremely rich mathematical object with deep and important connections to many areas, a few are listed in Andrei’s short introduction (mentioned below): quiver representations, preprojective algebras, Calabi-Yau algebras and categories,  Teichmüller theory, discrete integrable systems, Poisson geometry, and we can add also,  Somos sequences, alternating sign matrices, and, yet again, to associahedra and related classes of polytopes. A good place to start learning about cluster algebras is Andrei’s article from the Notices of the AMS: “What is a cluster algebra.” The cluster algebra portal can also be useful to keep track. And here is a very nice paper with a wide perspective called “integrable combinatorics”  by Phillippe Di Francesco. I should attempt a separate post for cluster algebras.

Andrei was a wonderful person and mathematician and I will miss him.

# Test Your Intuition (19): The Advantage of the Proposers in the Stable Matching Algorithm

### Stable mariage

The Gale-Shapley stable matching theorem and the algorithm.

GALE-SHAPLEY THEOREM Consider a society of n men and n women and suppose that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then there is a stable marriage, namely a perfect matching between the men and the women so that there are no men and women which are not matched so that both of them prefer the other on their spouces.

Proof: Consider the following algorithm, on day 1 every man goes to the first woman on his list and every woman select the best man among those who come to her and reject the others. On the second day every rejected men go to the second woman on his list and every woman select one man from all man that comes to her (including the man she selected in the previous day if there was such a man) and rejects all others, and so on. This process will terminate after finitely many days and with a stable marriage! To see that the process terminate note that each day at least one man will come to a new women, or go back home after beeing rejected from every women (n+1 possibilities) and none of these possibilitie will ever repeat itself so after at most $n^2+n$ days things will stabilize. When it terminates we have a stable marriage because suppose women W and men M are not married at the end. If M is married to a women he prefers less then W or to no women at all it means that M visited W and she rejected him so she had a better men than M.  Sababa!
It turns out that the above algorithm where the men are proposing and being rejected is optimal for the men! If a man M is matched to a woman W then there is not a single stable marriage where M can be matched to a woman higher on his list. Similarly this algorithm is worst for the women. But by how much?

### Random independent preferences

Question 1:  There are n men and n women. If the preferences are random and men are proposing, what is the likely average women’s rank of their husbands, and what is the likely average men’s rank of their wives.

You can test your intuition, or look at the answer and for a follow up question after the fold.