F Nous contacter


0

Documents  05Axx | enregistrements trouvés : 3

O
     

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

$k$-abelian singletons in connection with Gray codes for Necklaces. This work is based on [1]. We are interested in the equivalence classes induced by $k$-abelian equivalence, especially in the number of the classes containing only one element, $k$-abelian singletons. By characterizing $k$-abelian equivalence with $k$-switchings, a sort of rewriting operation, we are able to obtain a structural representation of $k$-abelian singletons. Analyzing this structural result leads, through rather technical considerations, to questions of certain properties of sets of vertex-disjoint cycles in the de Bruijn graph $dB_\Sigma(k-1)$ of order $k-1$. Some problems turn out to be equivalent to old open problems such as Gray codes for necklaces (or conjugacy classes). We shall formulate the problem in the following.
Let $\mathcal{C} = \lbrace V_1, . . . , V_n\rbrace$ be a cycle decomposition of $dB_\Sigma(n)$, that is, a partition of the vertex set $\Sigma^n$ into sets, each inducing a cycle or a loop in $dB_\Sigma(n)$. Let us then define the quotient graph $dB_\Sigma/\mathcal{C}$ as follows. The set of points are the sets in $\mathcal{C}$. For distinct sets $X, Y \in \mathcal{C}$, we have and edge from $X$ to $Y$ if and only if there exists $x{\in}X,y{\in}Y$ such that $(x,y){\in}dB_\Sigma(n)$. An old result shows that the size of a cycle decomposition of $dB_\Sigma(n)$ is at most the number of necklaces of length $n$ over $\Sigma$ (see [2]). We call a cycle decomposition maximal, if its size is maximal. In particular, the cycle decomposition given by necklaces is maximal.
Conjecture 1. For any $\Sigma$ and $n{\in}\mathbb{N}$, there exist a maximal cycle decomposition $\mathcal{C}$ of $dB_\Sigma(n)$ such that $dB_\Sigma(n)/\mathcal{C}$ contains a hamiltonian path.
A natural candidate to study here is the cycle decomposition given by necklaces. This has been studied in the literature in the connection of Gray codes for necklaces. Concerning this, there is an open problem since $1997$ $[3]$ : Let $\Sigma = \lbrace0, 1\rbrace$, $n$ odd, and $\mathcal{C}$ be the cycle decomposition given by necklaces of length $n$ over $\lbrace0,1\rbrace$. Does $dB(n)/\mathcal{C}$ contain a hamiltonian path ?
The answer to the above has been verified to be "yes" for $n \le 15$ $([1]$). The case of $n \ge 4$ and $n$ even, the graph is bipartite with one partition larger than the other. On the other hand, we can find other maximal cycle decompositions of $dB_\Sigma(4)$, $dB_\Sigma(6)$, and $dB_\Sigma(8)$ for the binary alphabet which all admit hamiltonian quotient graphs.
We concluded in $[1]$ that Conjecture $1$ is equivalent to the following $\Theta$-estimation of the number of $k$-abelian singletons of length $n$.
Conjecture 2. The number of $k$-abelian singletons of length $n$ over alphabet $\Sigma$ is of order $\Theta(n^{N_{\Sigma}(k-1)-1})$, where $N_\Sigma(l)$ is the number of necklaces of length $l$ over $\Sigma$.
$k$-abelian singletons in connection with Gray codes for Necklaces. This work is based on [1]. We are interested in the equivalence classes induced by $k$-abelian equivalence, especially in the number of the classes containing only one element, $k$-abelian singletons. By characterizing $k$-abelian equivalence with $k$-switchings, a sort of rewriting operation, we are able to obtain a structural representation of $k$-abelian singletons. Analyzing ...

68R15 ; 94B25 ; 05Axx

The $O(n)$ model can be formulated in terms of loops living on the lattice, with n the fugacity per loop. In two dimensions, it is known to possess a rich critical behavior, involving critical exponents varying continuously with n. In this talk, we will consider the case where the model is "coupled to 2D quantum gravity", namely it is defined on a random map.
It has been known since the 90's that the partition function of the model can be expressed as a matrix integral, which can be evaluated exactly in the planar limit. A few years ago, together with G. Borot and E. Guitter, we revisited the problem by a combinatorial approach, which allows to relate it to the so-called Boltzmann random maps, which have no loops but faces of arbitrary (and controlled) face degrees. In particular we established that the critical points of the $O(n)$ model are closely related to the "stable maps" introduced by Le Gall and Miermont.
After reviewing these results, I will move on to a more recent work done in collaboration with G. Borot and B. Duplantier, where we study the nesting statistics of loops. More precisely we consider loop configurations with two marked points and study the distribution of the number of loops separating them. The associated generating function can be computed exactly and, by taking asymptotics, we show that the number of separating loops grows logarithmically with the size of the maps at a (non generic) critical point, with an explicit large deviation function. Using a continuous generalization of the KPZ relation, our results are in full agreement with those of Miller, Watson and Wilson concerning nestings in Conformal Loop Ensembles.
The $O(n)$ model can be formulated in terms of loops living on the lattice, with n the fugacity per loop. In two dimensions, it is known to possess a rich critical behavior, involving critical exponents varying continuously with n. In this talk, we will consider the case where the model is "coupled to 2D quantum gravity", namely it is defined on a random map.
It has been known since the 90's that the partition function of the model can be ...

05Axx ; 60K35 ; 81T40

Multi angle  Combinatorics of Feynman integrals
Broadhurst, David (Auteur de la Conférence) | CIRM (Editeur )

Very recently, David Roberts and I have discovered wonderful conditions imposed on Feynman integrals by Betti and de Rham homology. In decoding the corresponding matrices, we encounter asymptotic expansions of a refined nature. In making sense of these, we appear to have some refuge in resurgence.

81T18 ; 05Axx

Nuage de mots clefs ici

Z