Open problems

Implementation of (planar) maps in sagemath (Julien Courtiel)

This "project" comes from a remark from Paul Melotti (UPMC), who deplored that the simple algorithms for planar maps were not implemented in sagemath, a free and open-source software for computer algebra system. Julien Courtiel (and other) proposed to address this problem by implementing some algorithms:

1. insert/remove a leaf
2. insert/remove/contract an edge
3. the transformation of a planar map into 4-valent maps/quadrangulations
4. the "Schaeffer's" bijection between maps and trees

During this discussion, one did the remark that sagemath has difficulties to deal with trees that are typed as graphs.

If anyone reading these lines is interested by this project, please contact Paul Melotti (melotti at posteo doht net) and Julien Courtiel (julien doht courtiel at unicaen doht fr).

A conjecture about Gatson-Watson tree (Fiona Skerman)

IT WAS DISPROVED BY MATTHIEU DIEN!

In any Gatson-Watson of size n, can we find a subtree of size > cn such that the depth of the root of the subtree is > c √n?

A conjecture about fusion of two "binary" trees (Clement Réquilé)

Let (S,T) be a pair of trees with n leaves, and such that each non-leaf vertex has degree 3. Take any perfect matching between the leaves of S and the leaves of T, and merge S and T by identifying the corresponding leaves. We denote by G[S,T] the resulting graph. Does there exist a constant c such that every possible G[S,T] has a non-intersecting cycle of length > cn?

Formula reminescence (Khaydar Nurligareev)

IT WAS SOLVED BY WENJIE FANG AND PIERRE−LOUIS GISCARD!

Do you recognize the following formula?

Minimum spanning tree for hypergraphs (Johanna Strömberg)

Can you define a notion of minimum spanning tree for hypergraphs? The ultimate goal is to study minimum spanning trees for random hypergraphs.

Conjecture about triangular lattice (Julien Courtiel)

IT WAS SOLVED BY IRENE MARCOVICI AND ANDREW ELVEY PRICE!

Consider a triangular lattice inside a triangle of size L. We can move inside this lattice with respect to 3 directions: East, Nord-West, South-West. (It's equivalent to the Goyou-Beauchamps model restricted to a right triangle of size L)

Fix a point P inside this triangular lattice, and n a length.

Conjecture. There are as many walks of length n starting from P as walks of length n ending to P.

Asymptotic estimate of some pairs of N-cycles (Elise Goujard)

Let C be a conjugacy class in the symmetric group S_N. What is the asymptotic behaviour of the number of pairs (h,v), where h and v are cycles of length N, and where hvh⁻¹v⁻¹ belongs to C?

Rombic-tiling sampling (Henri Derycke)

We would like to uniformly sample a random rombic-tiling on a hexagon. In particular, we would like to use some coupling from the past technique. A way to do this is to find an increasing poset over all rombic tilings. Is it possible to find such a structure?

Combinatorial interpretation of a recurrence (Katarzyna Grygiel)

The following families of combinatorial objects are in bijection:

• Black-white binary trees where the only authorized edges are: Black --(left child)--> White, White --(left child)--> Black, White --(left child)--> White, White --(right child)--> Black
• Binary trees with a forbidden pattern : O --(left child)--> O --(right child)--> O (the O's represent internal nodes)
• Some class of lambda-terms (sorry, I don't remember which ones exactly)

The cardinality of all these families satisfies the below recurrence. Is it possible to find a combinatorial interpretation of this formula? It would be useful to efficiently sample a random lambda-term.

Conjecture about lattices maximizing the number of tolerances (Katarzyna Grygiel)

Given a finite lattice, a tolerance is a reflexive, symmetric relation, consistent with min and max. For example, the N-chain, that is the lattice formed by a cascade of N elements, has Catalan(n-1) tolerances.

Conjecture. Among all n-elements lattices, chains are the richest with respect to the number of tolerances.