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 results

Filter
Select: All / None
Q
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y

The partially disjoint paths problem - Schrijver, Alexander (Author of the conference) | 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

Bookmarks Report an error
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Diagram groups and their geometry - lecture 2 - Genevois, Anthony (Author of the conference) | 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

Bookmarks Report an error
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y

Unramified graph covers of finite degree - Li, Winnie (Author of the conference) | 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

Bookmarks Report an error
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
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

Bookmarks Report an error
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y

The classification of excursions - Mishna, Marni (Author of the conference) | 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

Bookmarks Report an error
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
2y

Spectra of ultra-discrete limits - Zuk, Andrzej (Author of the conference) | CIRM H

Multi angle

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

37A30 ; 05C25 ; 35Q53 ; 20M35

Bookmarks Report an error
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Embeddings between RAAGs (part 1) - Genevois, Anthony (Author of the conference) | 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

Bookmarks Report an error