End of Lille 2012 workshop, problem session

1. Itai Benjamini

Take Gromov’s density model for random groups. Fix {k} generators. Pick independently and uniformly at random {N} relators of length {\ell}. Gromov shows that, when {\ell} is large, the quotient is infinite if {\log_{2k-1}N<\frac{1}{2}}. Zuk shows that the quotient has property (T) if {\log_{2k-1}N>\frac{1}{3}}.

As Linial explained to us for the Erdös-Renyi model, let us pick relators one after the other. What is the girth of the last infinite quotient ? Growth will collapse, but Girth should behave continuously.

2. Valerio Capraro

With Marco Scarsini, we study relations between game theory and amenable groups.

Recall that a countable group {G} is amenable iff it admits bi-invariant means (i.e. finitely additive probability measures).

Here is a 2-player game: Fix a subset {W\subset G}. P1 chooses {x_1\in G}. P2 chooses {x_2\in G}. P1 and P2 exchange 1 euro wether {x_1x_2 \in W} or not.

Does the game admit a Nash equilibrium ?

Our intuition is that, without further knowledge, players play “casually”, a notion which makes sens for amenable groups only.

Theorem 1 If {G} is amenable and if every left-invariant measure is also right-invariant (and conversely), then for all {W\subset G}, there are Nash equilibria given by bi-invariant means.

Question. Variational problem in amenable groups. Fix a left-invariant mean {\lambda}. Does the following functional on means attain its maximal ?

\displaystyle  \begin{array}{rcl}  \mu \mapsto \int\int\chi_W (xy)\,d\mu(x)\,d\lambda(y). \end{array}

Beware that Fubini does not hold for means. Also, the functional is not weakly continuous.

Question. Game theory characterization of amenable groups. Is it true that a countable group {G} is amenable if and only if for all {W\subset G}, there are Nash equilibria ?

3. Ryokichi Tanaka

Let {H^2} be hyperbolic plane. Consider a circle packing, and its contact graph. Perform simple random walk on it. When it is transient, what is the hitting distribution on the boundary circle ? Is it singular with respect to Lebesgue measure ?

When the packing is invariant under a Fuchsian group, harmonic measure may be singular.

4. Shalom Eliahou

I start with a hard and ancient problem, the Hadamard conjecture.

Definition 2 A Hadamard matrix is a square matrix with entries {\pm 1}, which is orthogonal up to factor {n}.

In 1893, Jacques Hadamard conjectured that Hadamard matrices exist for all sizes {n\in 4{\mathbb N}}. The least open case is 668.

I am interested in a weaker form, where one merely requires that {H H^{\top}=nI} mod {m}. This was introduced by Marrero and Butson in 1972. They give a positive answer for {m=6} and {m=12}. This is easy.

In 2001, with Michel Kervaire, I gave a positive answer for {m=32}. It is harder: we provide a list which is a mixture of successful guesses, algebra, number theory. What about {m=64} ? I hope it is

5. Nati Linial

5.1. Continuation

Here is an other relaxation of Hadamard’s conjecture.

What is the least {f(n)} for which it can be shown that there exists {n\times n} {\pm1} matrices which each inner product is between {\pm f(n)}.

5.2. Signings

Let {G} be a {d}-regular graph. A signing of {G} is a symmetric matrix {B} that is obtained by putting {\pm1}‘s on the entries of {G}‘s adjacency matrix.

Conjecture. Every {d}-regular graph has a signing with spectral radius {\leq 2\sqrt{d-1}}.

If it holds, then there exist Ramanujan graphs of arbitrarily large size. Indeed, a signing is a specification for a double cover of {G}, and the spectrum of {B} resflects the new eigenvalues occuring for that graph. If {G} was Ramanujan, so is the cover.

5.3. Improving on the Moore bound

Easy: A {d}-regular {n}-vertex graph has girth at most {2\frac{\log n}{\log(d-1)}}.

Conjecture. The factor of {2} is not optimal.

Moore’s bound is an equality for finitely many graphs.

Random graphs have short cycles. Solving the conjecture for Cayley graphs would be interesting.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s