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:
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).
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?
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?
IT WAS SOLVED BY WENJIE FANG AND PIERRE−LOUIS GISCARD!
Do you recognize the following formula?
Let aₖ(w) be a random variable such that the probability of aₖ(w) = m is equal to 2⁻ᵐ⁻¹ (m ≥ 0).
Consider qₖ(w) a random sequence defined by q₀ = 1 and q₋₁ = 0 and by the opposite recurrence.
What can you say about the limit of the dyadic valuation of qₖ(w)? Can you prove that it behaves like ~ c k?
Can you define a notion of minimum spanning tree for hypergraphs? The ultimate goal is to study minimum spanning trees for random hypergraphs.
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.
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?
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?
The following families of combinatorial objects are in bijection:
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.
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.