F Nous contacter


0

Combinatorics  | enregistrements trouvés : 72

O

-A +A

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

P Q

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

- 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

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

In the first half of the talk, I will survey results and open problems on transience of self-interacting martingales. In particular, I will describe joint works with S. Popov, P. Sousi, R. Eldan and F. Nazarov on the tradeoff between the ambient dimension and the number of different step distributions needed to obtain a recurrent process. In the second, unrelated, half of the talk, I will present joint work with Tom Hutchcroft, showing that the component structure of the uniform spanning forest in $\mathbb{Z}^d$ changes every dimension for $d > 8$. This sharpens an earlier result of Benjamini, Kesten, Schramm and the speaker (Annals Math 2004), where we established a phase transition every four dimensions. The proofs are based on a the connection to loop-erased random walks. In the first half of the talk, I will survey results and open problems on transience of self-interacting martingales. In particular, I will describe joint works with S. Popov, P. Sousi, R. Eldan and F. Nazarov on the tradeoff between the ambient dimension and the number of different step distributions needed to obtain a recurrent process. In the second, unrelated, half of the talk, I will present joint work with Tom Hutchcroft, showing that the ...

05C05 ; 05C80 ; 60G50 ; 60J10 ; 60K35 ; 82B43

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

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

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

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

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

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

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

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

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

Rooted connected chord diagrams can be used to index certain expansions in quantum field theory. There is also a nice bijection between rooted connected chord diagrams and bridgeless maps. I will discuss each of these things as well as how the second sheds light on the first. (Based on work with Nicolas Marie, Markus Hihn, Julien Courtiel, and Noam Zeilberger.)

81T15 ; 81T18 ; 05C80

Multi angle  Pseudo-Anosov braids are generic
Wiest, Bert (Auteur de la Conférence) | CIRM (Editeur )

We prove that generic elements of braid groups are pseudo-Anosov, in the following sense: in the Cayley graph of the braid group with $n\geq 3$ strands, with respect to Garside's generating set, we prove that the proportion of pseudo-Anosov braids in the ball of radius $l$ tends to $1$ exponentially quickly as $l$ tends to infinity. Moreover, with a similar notion of genericity, we prove that for generic pairs of elements of the braid group, the conjugacy search problem can be solved in quadratic time. The idea behind both results is that generic braids can be conjugated ''easily'' into a rigid braid.
braid groups - Garside groups - Nielsen-Thurston classification - pseudo-Anosov - conjugacy problem
We prove that generic elements of braid groups are pseudo-Anosov, in the following sense: in the Cayley graph of the braid group with $n\geq 3$ strands, with respect to Garside's generating set, we prove that the proportion of pseudo-Anosov braids in the ball of radius $l$ tends to $1$ exponentially quickly as $l$ tends to infinity. Moreover, with a similar notion of genericity, we prove that for generic pairs of elements of the braid group, the ...

20F36 ; 20F10 ; 20F65

$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

Multi angle  Random walks on dynamical percolation
Sousi, Perla (Auteur de la Conférence) | CIRM (Editeur )

We study the behaviour of random walk on dynamical percolation. In this model, the edges of a graph are either open or closed and refresh their status at rate $\mu$, while at the same time a random walker moves on $G$ at rate 1, but only along edges which are open. On the d-dimensional torus with side length $n$, when the bond parameter is subcritical, the mixing times for both the full system and the random walker were determined by Peres, Stauffer and Steif. I will talk about the supercritical case, which was left open, but can be analysed using evolving sets.

Joint work with Y. Peres and J. Steif.
We study the behaviour of random walk on dynamical percolation. In this model, the edges of a graph are either open or closed and refresh their status at rate $\mu$, while at the same time a random walker moves on $G$ at rate 1, but only along edges which are open. On the d-dimensional torus with side length $n$, when the bond parameter is subcritical, the mixing times for both the full system and the random walker were determined by Peres, ...

60K35 ; 60J10 ; 60G50 ; 82B43

Multi angle  Incidences in Cartesian products
Solymosi, Jozsef (Auteur de la Conférence) | CIRM (Editeur )

Various problems in additive combinatorics can be translated to a question about incidences in Cartesian products. A well known example is Elekes' treatment of the sum-product problem but there are many more applications of incidence bounds to arithmetic problems. I will review the classical applications and show some recent results.

11B75 ; 11B13 ; 52C10 ; 05Dxx

Z