En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK

Documents 05C25 7 résultats

Filtrer
Sélectionner : Tous / Aucun
Q
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y

The partially disjoint paths problem - Schrijver, Alexander (Auteur de la Conférence) | CIRM H

Post-edited

The partially disjoint paths problem asks for paths $P_1, \ldots,P_k$ between given pairs of terminals, while certain pairs of paths $P_i$,$P_j$ are required to be disjoint. With the help of combinatorial group theory, we show that, for fixed $k$, this problem can be solved in polynomial time for planar directed graphs. We also discuss related problems. No specific foreknowledge is required.

05C10 ; 05C20 ; 05C25 ; 05C38 ; 68Q25 ; 90C27

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Diagram groups and their geometry - lecture 2 - Genevois, Anthony (Auteur de la Conférence) | CIRM H

Multi angle

In these talks, we will discuss a family of groups called diagram groups, studied extensively by Guba and Sapir and others. These depend on semigroup presentations and turn out to have many good algorithmic properties. The first lecture will be a survey of diagram groups, including several examples and generalizations. The second lecture will take a geometric approach, understanding these groups through median-like geometry.

20F65 ; 05C25 ; 57M07

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y

Unramified graph covers of finite degree - Li, Winnie (Auteur de la Conférence) | CIRM H

Post-edited

Given a finite connected undirected graph $X$, its fundamental group plays the role of the absolute Galois group of $X$. The familiar Galois theory holds in this setting. In this talk we shall discuss graph theoretical counter parts of several important theorems for number fields. Topics include
(a) Determination, up to equivalence, of unramified normal covers of $X$ of given degree,
(b) Criteria for Sunada equivalence,
(c) Chebotarev density theorem.
This is a joint work with Hau-Wen Huang.[-]
Given a finite connected undirected graph $X$, its fundamental group plays the role of the absolute Galois group of $X$. The familiar Galois theory holds in this setting. In this talk we shall discuss graph theoretical counter parts of several important theorems for number fields. Topics include
(a) Determination, up to equivalence, of unramified normal covers of $X$ of given degree,
(b) Criteria for Sunada equivalence,
(c) Chebotarev density ...[+]

05C25 ; 05C50 ; 11R32 ; 11R44 ; 11R45

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

The diameter of the symmetric group: ideas and tools - Helfgott, Harald (Auteur de la Conférence) | CIRM H

Multi angle

Given a finite group $G$ and a set $A$ of generators, the diameter diam$(\Gamma(G, A))$ of the Cayley graph $\Gamma(G, A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding diam$(G) := max_A$ diam$(\Gamma(G, A))$.
It has long been conjectured that the diameter of the symmetric group of degree $n$ is polynomially bounded in $n$. In 2011, Helfgott and Seress gave a quasipolynomial bound, namely, $O\left (e^{(log n)^{4+\epsilon}}\right )$. We will discuss a recent, much simplified version of the proof.[-]
Given a finite group $G$ and a set $A$ of generators, the diameter diam$(\Gamma(G, A))$ of the Cayley graph $\Gamma(G, A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding diam$(G) := max_A$ diam$(\Gamma(G, A))$.
It has long been conjectured that the diameter of the symmetric group of degree $n$ is polynomially bounded in $n$. In 2011, ...[+]

20B05 ; 05C25 ; 20B30 ; 20F69 ; 20D60

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y

The classification of excursions - Mishna, Marni (Auteur de la Conférence) | CIRM H

Multi angle

Excursions are walks which start and end at prescribed locations. In this talk we consider the counting sequences of excursions, more precisely, the functional equations their generating functions satisfy. We focus on two sources of excursion problems: walks defined by their allowable steps, taken on integer lattices restricted to cones; and walks on Cayley graphs with a given set of generators. The latter is related to the cogrowth problems of groups. In both cases we are interested in relating the nature of the generating function (i.e. rational, algebraic, D-finite, etc.) and combinatorial properties of the models. We are also interested in the relation between the excursions, and less restricted families of walks.
Please note: A few corrections were made to the PDF file of this talk, the new version is available at the bottom of the page.[-]
Excursions are walks which start and end at prescribed locations. In this talk we consider the counting sequences of excursions, more precisely, the functional equations their generating functions satisfy. We focus on two sources of excursion problems: walks defined by their allowable steps, taken on integer lattices restricted to cones; and walks on Cayley graphs with a given set of generators. The latter is related to the cogrowth problems of ...[+]

05A15 ; 05C25 ; 60G50 ; 20F05

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y

Spectra of ultra-discrete limits - Zuk, Andrzej (Auteur de la Conférence) | CIRM H

Multi angle

We present a computation of spectra of random walks on self-similar graphs.

37A30 ; 05C25 ; 35Q53 ; 20M35

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Embeddings between RAAGs (part 1) - Genevois, Anthony (Auteur de la Conférence) | CIRM H

Multi angle

Right-angled Artin groups, aka partially commutative groups, naturally define an interpolation between free groups and abelian free groups. The mini-course is dedicated to the question: given two right-angled Artin groups, how can we know whether one is isomorphic to a subgroup of the other? Even though this is a basic algebraic question, it remains widely open in full generality. Our goal will be to show how the combinatorial geometry of quasi-median graphs hilights some aspects of this problem. [-]
Right-angled Artin groups, aka partially commutative groups, naturally define an interpolation between free groups and abelian free groups. The mini-course is dedicated to the question: given two right-angled Artin groups, how can we know whether one is isomorphic to a subgroup of the other? Even though this is a basic algebraic question, it remains widely open in full generality. Our goal will be to show how the combinatorial geometry of ...[+]

20F65 ; 05C25 ; 20F67

Sélection Signaler une erreur