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

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.