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

Combinatorics 238 results

Filter
Select: All / None
Q
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
We show how to construct 'simple' symbolic dynamical systems in terms of renormalisation schemes associated with multidimensional continued fractions. Continued fractions are used here to generate infinite words thanks to the iteration of infinite sequences of substitutions. Simple means that these symbolic systems have a linear number of factors of a given length, or that they have pure discrete spectrum, or else, that they have a low symbolic discrepancy. We also discuss the relation between these notions.[-]
We show how to construct 'simple' symbolic dynamical systems in terms of renormalisation schemes associated with multidimensional continued fractions. Continued fractions are used here to generate infinite words thanks to the iteration of infinite sequences of substitutions. Simple means that these symbolic systems have a linear number of factors of a given length, or that they have pure discrete spectrum, or else, that they have a low symbolic ...[+]

37B10 ; 11K50 ; 68R15

Bookmarks Report an error
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
We consider the assignment (or bipartite matching) problem between $n$ source points and $n$ target points on the real line, where the assignment cost is a concave power of the distance, i.e. |x − y|p, for 0 < p < 1. It is known that, differently from the convex case (p > 1) where the solution is rigid, i.e. it does not depend on p, in the concave case it may varies with p and exhibit interesting long-range connections, making it more appropriate to model realistic situations, e.g. in economics and biology. In the random version of the problem, the points are samples of i.i.d. random variables, and one is interested in typical properties as the sample size n grows. Barthe and Bordenave in 2013 proved asymptotic upper and lower bounds in the range 0 < p < 1/2, which they conjectured to be sharp. Bobkov and Ledoux, in 2020, using optimal transport and Fourier-analytic tools, determined explicit upper bounds for the average assignment cost in the full range 0 < p < 1, naturally yielding to the conjecture that a “phase transition” occurs at p = 1/2. We settle affirmatively both conjectures. The novel mathematical tool that we develop, and may be of independent interest, is a formulation of Kantorovich problem based on Young integration theory, where the difference between two measures is replaced by the weak derivative of a function with finite q-variation.
Joint work with M. Goldman (arXiv:2305.09234).[-]
We consider the assignment (or bipartite matching) problem between $n$ source points and $n$ target points on the real line, where the assignment cost is a concave power of the distance, i.e. |x − y|p, for 0 < p 1) where the solution is rigid, i.e. it does not depend on p, in the concave case it may varies with p and exhibit interesting long-range connections, making it more appropriate to model realistic situations, e.g. in economics a...[+]

49Q22 ; 60D05 ; 60L99

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.
y

Complexity and the hat - Goodman-Strauss , Chaim (Author of the conference) | CIRM H

Multi angle

The recent discovery of the “hat”, an aperiodic monotile points to the complexity that can be encoded within even a simple shape – might it even be undecidable whether or not a given shape can be used to form a tiling of the plane? We'll survey related this and related questions for tiles and subshifts of finite type in the plane and other geometric spaces.

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

An introduction to Walnut - lecture 1 - Rampersad, Narad (Author of the conference) | CIRM H

Multi angle

Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for participants to get some hands-on training on how to use Walnut.[-]
Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for ...[+]

68R15 ; 68Q45 ; 03F30

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

An introduction to Walnut - lecture 2 - Rampersad, Narad (Author of the conference) | CIRM H

Multi angle

Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for participants to get some hands-on training on how to use Walnut.[-]
Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for ...[+]

68R15 ; 68Q45 ; 03F30

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

Domino snake problems on groups - Aubrun, Nathalie (Author of the conference) | CIRM H

Multi angle

Wang's tiles were introduced in the 1960s and have been an inexhaustible source of undecidable problems ever since. They are unit square tiles with colored edges and fixed orientation, which can be placed together provided they share the same color on their common edge. Many decision problems involving Wang tiles follow the same global structure: given a finite set of Wang tiles, is there an algorithm to determine if they tile a particular shape or subset of the infinite grid? If we look for a tiling of the whole grid, this is the domino problem which is known to be undecidable for Z2 and many other groups. In this talk we focus on infinite snake tilings. Originally the infinite snake problem asks is there exists a tiling of a self-avoiding bi-infinite path on the grid Z2. In this talk I present how to expand the scope of domino snake problems to finitely generated groups to understand how the underlying structure affects computability. This is joint work with Nicolás Bitar.[-]
Wang's tiles were introduced in the 1960s and have been an inexhaustible source of undecidable problems ever since. They are unit square tiles with colored edges and fixed orientation, which can be placed together provided they share the same color on their common edge. Many decision problems involving Wang tiles follow the same global structure: given a finite set of Wang tiles, is there an algorithm to determine if they tile a particular shape ...[+]

05B45 ; 03D80 ; 37B10

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

String attractors of Rote sequences - Hendrychová, Veronika (Author of the conference) | CIRM H

Multi angle

String attractor, a relatively new combinatorial notion, is closely related to measuring the complexity of words and offers a unified approach to the repetitiveness measures induced by dictionary compressors. However, attractors have been only little studied in the context of combinatorics on words, particularly for classes of low complexity, including complementary-symmetric Rote sequences. In this talk, we work with pseudopalindromic closures as a useful way to generate these sequences, and then show the form of minimal attractors of their pseudopalindromic prefixes.[-]
String attractor, a relatively new combinatorial notion, is closely related to measuring the complexity of words and offers a unified approach to the repetitiveness measures induced by dictionary compressors. However, attractors have been only little studied in the context of combinatorics on words, particularly for classes of low complexity, including complementary-symmetric Rote sequences. In this talk, we work with pseudopalindromic closures ...[+]

68R15 ; 68P30 ; 68R05

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

Around Cobham's theorem - Krawczyk, Elzbieta (Author of the conference) | CIRM H

Multi angle

We provide a complete characterisation of automaticity of uniformly recurrent substitutive sequences in terms of the incidence matrix of the return substitution of an underlying purely substitutive sequence. This gives an answer to a recent question of Allouche, Dekking and Queffélec in the uniformly recurrent case.

11B85 ; 37B10 ; 68R15

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

Thue choice number and the counting argument - Rosenfeld, Matthieu (Author of the conference) | CIRM H

Multi angle

I recently introduced a new proof technique based on a simple counting argument that I applied to many problems from combinatorics. In this talk, I will illustrate this counting argument with a proof that the Thue choice number is at most 4. Suppose we have to construct a square-free word (ie, no non-empty factors is of the form uu) by chosing the letter of each position of the word from an alphabet specific to the position. The Thue choice number is the smallest k such that, if all these alphabets have size at least k, then we can build an infinite square-free word.
I will then present how it can be pushed further in the context of combinatorics on words.[-]
I recently introduced a new proof technique based on a simple counting argument that I applied to many problems from combinatorics. In this talk, I will illustrate this counting argument with a proof that the Thue choice number is at most 4. Suppose we have to construct a square-free word (ie, no non-empty factors is of the form uu) by chosing the letter of each position of the word from an alphabet specific to the position. The Thue choice ...[+]

68R05 ; 05D40 ; 68R15

Bookmarks Report an error