F Nous contacter


0

Combinatorics  | enregistrements trouvés : 66

O

-A +A

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

P Q

We will cover some of the more important results from commutative and noncommutative algebra as far as applications to automatic sequences, pattern avoidance, and related areas. Well give an overview of some applications of these areas to the study of automatic and regular sequences and combinatorics on words.

11B85 ; 68Q45 ; 68R15

La décomposition par substitution des permutations permet de voir ces objets combinatoires comme des arbres. Je présenterai d'abord cette décomposition par substitution, et les arbres sous-jacents, appelés arbres de décomposition. Puis j'exposerai une méthode, complètement algorithmique et reposant sur les arbres de décomposition, qui permet de calculer des spécifications combinatoires de classes de permutations à motifs interdits. La connaissance de telles spécifications combinatoires ouvre de nouvelles perspectives pour l'étude des classes de permutations, que je présenterai en conclusion. La décomposition par substitution des permutations permet de voir ces objets combinatoires comme des arbres. Je présenterai d'abord cette décomposition par substitution, et les arbres sous-jacents, appelés arbres de décomposition. Puis j'exposerai une méthode, complètement algorithmique et reposant sur les arbres de décomposition, qui permet de calculer des spécifications combinatoires de classes de permutations à motifs interdits. La c...

68-06 ; 05A05

Post-edited  Coloring graphs on surfaces
Esperet, Louis (Auteur de la Conférence) | CIRM (Editeur )

Post-edited  Le problème Graph Motif - Partie 1
Fertin, Guillaume (Auteur de la Conférence) | CIRM (Editeur )

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

05C15 ; 05C85 ; 05C90 ; 68Q17 ; 68Q25 ; 68R10 ; 92C42 ; 92D20

We will consider (sub)shifts with complexity such that the difference from $n$ to $n+1$ is constant for all large $n$. The shifts that arise naturally from interval exchange transformations belong to this class. An interval exchange transformation on d intervals has at most $d/2$ ergodic probability measures. We look to establish the correct bound for shifts with constant complexity growth. To this end, we give our current bound and discuss further improvements when more assumptions are allowed. This is ongoing work with Michael Damron. We will consider (sub)shifts with complexity such that the difference from $n$ to $n+1$ is constant for all large $n$. The shifts that arise naturally from interval exchange transformations belong to this class. An interval exchange transformation on d intervals has at most $d/2$ ergodic probability measures. We look to establish the correct bound for shifts with constant complexity growth. To this end, we give our current bound and discuss ...

37B10 ; 37A25 ; 68R15

I will discuss recent progress on understanding the dimension of self-similar sets and measures. The main conjecture in this field is that the only way that the dimension of such a fractal can be "non-full" is if the semigroup of contractions which define it is not free. The result I will discuss is that "non-full" dimension implies "almost non-freeness", in the sense that there are distinct words in the semigroup which are extremely close together (super-exponentially in their lengths). Applications include resolution of some conjectures of Furstenberg on the dimension of sumsets and, together with work of Shmerkin, progress on the absolute continuity of Bernoulli convolutions. The main new ingredient is a statement in additive combinatorics concerning the structure of measures whose entropy does not grow very much under convolution. If time permits I will discuss the analogous results in higher dimensions. I will discuss recent progress on understanding the dimension of self-similar sets and measures. The main conjecture in this field is that the only way that the dimension of such a fractal can be "non-full" is if the semigroup of contractions which define it is not free. The result I will discuss is that "non-full" dimension implies "almost non-freeness", in the sense that there are distinct words in the semigroup which are extremely close ...

28A80 ; 37A10 ; 03D99 ; 54H20

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

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

Post-edited  Descriptive graph combinatorics. Lecture 1
Marks, Andrew (Auteur de la Conférence) | CIRM (Editeur )

A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold. A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we ...

05C50 ; 05C80 ; 68T05 ; 91D30

The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in between?
With Alex Scott, we recently proved the following, a 1985 conjecture of Gyárfás:

For graphs $G$ with no odd hole, $\chi(G)$ is bounded by a function of $\omega(G)$.

Gyárfás also made the stronger conjecture that for every integer $k$ and for all graphs $G$ with no odd hole of length more than $k$, $\chi(G)$ is bounded by a function of $k$ and $\omega(G)=2$. This is far from settled, and indeed the following much weaker statement is not settled: for every integer $k$, every triangle-free graph with no hole of length at least $k$ has chromatic number bounded by a function of $k$. We give a partial result towards the latter:

For all $k$, every triangle-free graph with no hole of length at least $k$ admits a tree-decomposition into bags with chromatic number bounded by a function of $k$.

Both results have quite pretty proofs, which will more-or-less be given in full.
The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in ...

05C15 ; 05C35 ; 05C85

- Normalized characters of the symmetric groups,
- Kerov polynomials and Kerov positivity conjecture,
- Stanley character polynomials and multirectangular coordinates of Young diagrams,
- Stanley character formula and maps,
- Jack characters
- characterization, partial results.

05E10 ; 05E15 ; 20C30 ; 05A15 ; 05C10

Erdös and Sárközy asked the maximum size of a subset of the first $N$ integers with no two elements adding up to a perfect square. In this talk we prove that the tight answer is $\frac{11}{32}N$ for sufficiently large $N$. We are going to prove some stability results also. This is joint work with Simao Herdade and Ayman Khalfallah.

05A18 ; 11B75

Multi angle  Recurrence of half plane maps
Angel, Omer (Auteur de la Conférence) | CIRM (Editeur )

On a graph $G$, we consider the bootstrap model: some vertices are infected and any vertex with 2 infected vertices becomes infected. We identify the location of the threshold for the event that the Erdos-Renyi graph $G(n, p)$ can be fully infected by a seed of only two infected vertices. Joint work with Brett Kolesnik.

05C80 ; 60K35 ; 60C05

We prove that a measure on $[-d,d]$ is the spectral measure of a factor of i.i.d. process on a vertex-transitive infinite graph if and only if it is absolutely continuous with respect to the spectral measure of the graph. Moreover, we show that the set of spectral measures of factor of i.i.d. processes and that of $\bar{d}_2$-limits of factor of i.i.d. processes are the same.

05C80 ; 60G15

Multi angle  Amenable groups - Lecture 2
Bartholdi, Laurent (Auteur de la Conférence) | CIRM (Editeur )

I shall discuss old and new results on amenability of groups, and more generally G-sets. This notion traces back to von Neumann in his study of the Hausdorff-Banach-Tarski paradox, and grew into one of the fundamental properties a group may / may not have -- each time with important consequences.
Lecture 1. I will present the classical notions and equivalent definitions of amenability, with emphasis on group actions and on combinatorial aspects: Means, Folner sets, random walks, and paradoxical decompositions.
Lecture 2. I will describe recent work by de la Salle et al. leading to a quite general criterion for amenability, as well as some still open problems. In particular, I will show that full topological groups of minimal Z-shifts are amenable.
Lecture 3. I will explain links between amenability and cellular automata, in particular the "Garden of Eden" properties by Moore and Myhill: there is a characterization of amenable groups in terms of whether these classical theorems still hold.
I shall discuss old and new results on amenability of groups, and more generally G-sets. This notion traces back to von Neumann in his study of the Hausdorff-Banach-Tarski paradox, and grew into one of the fundamental properties a group may / may not have -- each time with important consequences.
Lecture 1. I will present the classical notions and equivalent definitions of amenability, with emphasis on group actions and on combinatorial aspects: ...

37B15 ; 37B10 ; 43A07 ; 68Q80

Erdös and Rényi introduced a model for studying random graphs of a given "density" and proved that there is a sharp threshold at which lower density random graphs are disconnected and higher density ones are connected. Motivated by ideas in geometric group theory we will explain some new threshold theorems we have discovered for random graphs. We will then explain applications of these results to the geometry of Coxeter groups. Some of this talk will be on joint work with Hagen and Sisto; other parts are joint work with Hagen, Susse, and Falgas-Ravry. Erdös and Rényi introduced a model for studying random graphs of a given "density" and proved that there is a sharp threshold at which lower density random graphs are disconnected and higher density ones are connected. Motivated by ideas in geometric group theory we will explain some new threshold theorems we have discovered for random graphs. We will then explain applications of these results to the geometry of Coxeter groups. Some of this talk ...

05C80 ; 20F65

* The early results of Ramsey theory :

Hilbert's irreducibility theorem, Dickson-Schur work on Fermat's equation over finite fields, van der Waerden's theorem, Ramsey's theoremand its rediscovery by Erdos and Szekeres.


* Three main principles of Ramsey theory :

First principle: Complete disorder is impossible. Second principle: Behind every 'Partition' result there is a notion of largeness which is responsible for a 'Density' enhancement of this result. Third principle: The sought-after configurations which are always to be found in large sets are abundant.


* Furstenberg's Dynamical approach :

Partition Ramsey theory and topological dynamics Dynamical versions of van der Waerden's theorem, Hindman's theorem and Graham-Rothschild-Spencer's geometric Ramsey.
Density Ramsey theory and Furstenberg's correspondence principle Furstenberg's correspondence principle. Ergodic Szemeredi's theorem. Polynomial Szemeredi theorem. Density version of the Hales-Jewett theorem.


* Stone-Cech compactifications and Hindman's theorem :

Topological algebra in Stone-Cech compactifications. Proof of Hind-man's theorem via Poincare recurrence theorem for ultrafilters.


* IP sets and ergodic Ramsey theory :

Applications of IP sets and idempotent ultrafilters to ergodic-theoretical multiple recurrence and to density Ramsey theory. IP-polynomial Szemeredi theorem.


* Open problems and conjectures


If time permits: * The nilpotent connection, * Ergodic Ramsey theory and amenable groups
* The early results of Ramsey theory :

Hilbert's irreducibility theorem, Dickson-Schur work on Fermat's equation over finite fields, van der Waerden's theorem, Ramsey's theoremand its rediscovery by Erdos and Szekeres.


* Three main principles of Ramsey theory :

First principle: Complete disorder is impossible. Second principle: Behind every 'Partition' result there is a notion of largeness which is responsible for a 'Density' enhancement of ...

05D10 ; 37Axx ; 12D10 ; 11D41 ; 54D80 ; 37B20

* The early results of Ramsey theory :

Hilbert's irreducibility theorem, Dickson-Schur work on Fermat's equation over finite fields, van der Waerden's theorem, Ramsey's theoremand its rediscovery by Erdos and Szekeres.


* Three main principles of Ramsey theory :

First principle: Complete disorder is impossible. Second principle: Behind every 'Partition' result there is a notion of largeness which is responsible for a 'Density' enhancement of this result. Third principle: The sought-after configurations which are always to be found in large sets are abundant.


* Furstenberg's Dynamical approach :

Partition Ramsey theory and topological dynamics Dynamical versions of van der Waerden's theorem, Hindman's theorem and Graham-Rothschild-Spencer's geometric Ramsey.
Density Ramsey theory and Furstenberg's correspondence principle Furstenberg's correspondence principle. Ergodic Szemeredi's theorem. Polynomial Szemeredi theorem. Density version of the Hales-Jewett theorem.


* Stone-Cech compactifications and Hindman's theorem :

Topological algebra in Stone-Cech compactifications. Proof of Hind-man's theorem via Poincare recurrence theorem for ultrafilters.


* IP sets and ergodic Ramsey theory :

Applications of IP sets and idempotent ultrafilters to ergodic-theoretical multiple recurrence and to density Ramsey theory. IP-polynomial Szemeredi theorem.


* Open problems and conjectures


If time permits: * The nilpotent connection, * Ergodic Ramsey theory and amenable groups
* The early results of Ramsey theory :

Hilbert's irreducibility theorem, Dickson-Schur work on Fermat's equation over finite fields, van der Waerden's theorem, Ramsey's theoremand its rediscovery by Erdos and Szekeres.


* Three main principles of Ramsey theory :

First principle: Complete disorder is impossible. Second principle: Behind every 'Partition' result there is a notion of largeness which is responsible for a 'Density' enhancement of ...

05D10 ; 37Axx ; 12D10 ; 11D41 ; 54D80 ; 37B20

* The early results of Ramsey theory :

Hilbert's irreducibility theorem, Dickson-Schur work on Fermat's equation over finite fields, van der Waerden's theorem, Ramsey's theoremand its rediscovery by Erdos and Szekeres.


* Three main principles of Ramsey theory :

First principle: Complete disorder is impossible. Second principle: Behind every 'Partition' result there is a notion of largeness which is responsible for a 'Density' enhancement of this result. Third principle: The sought-after configurations which are always to be found in large sets are abundant.


* Furstenberg's Dynamical approach :

Partition Ramsey theory and topological dynamics Dynamical versions of van der Waerden's theorem, Hindman's theorem and Graham-Rothschild-Spencer's geometric Ramsey.
Density Ramsey theory and Furstenberg's correspondence principle Furstenberg's correspondence principle. Ergodic Szemeredi's theorem. Polynomial Szemeredi theorem. Density version of the Hales-Jewett theorem.


* Stone-Cech compactifications and Hindman's theorem :

Topological algebra in Stone-Cech compactifications. Proof of Hind-man's theorem via Poincare recurrence theorem for ultrafilters.


* IP sets and ergodic Ramsey theory :

Applications of IP sets and idempotent ultrafilters to ergodic-theoretical multiple recurrence and to density Ramsey theory. IP-polynomial Szemeredi theorem.


* Open problems and conjectures


If time permits: * The nilpotent connection, * Ergodic Ramsey theory and amenable groups
* The early results of Ramsey theory :

Hilbert's irreducibility theorem, Dickson-Schur work on Fermat's equation over finite fields, van der Waerden's theorem, Ramsey's theoremand its rediscovery by Erdos and Szekeres.


* Three main principles of Ramsey theory :

First principle: Complete disorder is impossible. Second principle: Behind every 'Partition' result there is a notion of largeness which is responsible for a 'Density' enhancement of ...

05D10 ; 37Axx ; 12D10 ; 11D41 ; 54D80 ; 37B20

* The early results of Ramsey theory :

Hilbert's irreducibility theorem, Dickson-Schur work on Fermat's equation over finite fields, van der Waerden's theorem, Ramsey's theoremand its rediscovery by Erdos and Szekeres.


* Three main principles of Ramsey theory :

First principle: Complete disorder is impossible. Second principle: Behind every 'Partition' result there is a notion of largeness which is responsible for a 'Density' enhancement of this result. Third principle: The sought-after configurations which are always to be found in large sets are abundant.


* Furstenberg's Dynamical approach :

Partition Ramsey theory and topological dynamics Dynamical versions of van der Waerden's theorem, Hindman's theorem and Graham-Rothschild-Spencer's geometric Ramsey.
Density Ramsey theory and Furstenberg's correspondence principle Furstenberg's correspondence principle. Ergodic Szemeredi's theorem. Polynomial Szemeredi theorem. Density version of the Hales-Jewett theorem.


* Stone-Cech compactifications and Hindman's theorem :

Topological algebra in Stone-Cech compactifications. Proof of Hind-man's theorem via Poincare recurrence theorem for ultrafilters.


* IP sets and ergodic Ramsey theory :

Applications of IP sets and idempotent ultrafilters to ergodic-theoretical multiple recurrence and to density Ramsey theory. IP-polynomial Szemeredi theorem.


* Open problems and conjectures


If time permits: * The nilpotent connection, * Ergodic Ramsey theory and amenable groups
* The early results of Ramsey theory :

Hilbert's irreducibility theorem, Dickson-Schur work on Fermat's equation over finite fields, van der Waerden's theorem, Ramsey's theoremand its rediscovery by Erdos and Szekeres.


* Three main principles of Ramsey theory :

First principle: Complete disorder is impossible. Second principle: Behind every 'Partition' result there is a notion of largeness which is responsible for a 'Density' enhancement of ...

05D10 ; 37Axx ; 12D10 ; 11D41 ; 54D80 ; 37B20

Z