In memoriam: Philippe Flajolet, the father of analytic combinatorics
In memoriam: Philippe Flajolet, the father of analytic combinatorics
Independence number and degree bounded spanning tree.
INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
Independent sets on path-schemes.
Inductive computations on graphs defined by clique-width expressions
Labelling problems for graphs consist in building distributed data structures, making it possible to check a given graph property or to compute a given function, the arguments of which are vertices. For an inductively computable function D, if G is a graph with n vertices and of clique-width at most k, where k is fixed, we can associate with each vertex x of G a piece of information (bit sequence) lab(x) of length O(log2(n)) such that we can compute D in constant time, using only the labels...
Infinite periodic discrete minimal surfaces without self-intersections.
Infinite periodic points of endomorphisms over special confluent rewriting systems
We consider endomorphisms of a monoid defined by a special confluent rewriting system that admit a continuous extension to the completion given by reduced infinite words, and study from a dynamical viewpoint the nature of their infinite periodic points. For prefix-convergent endomorphisms and expanding endomorphisms, we determine the structure of the set of all infinite periodic points in terms of adherence values, bound the periods and show that all regular periodic points are attractors.
Infinite words containing squares at every position
Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is α = 7/3.
Influence of modeling structure in probabilistic sequential decision problems
Markov Decision Processes (MDPs) are a classical framework for stochastic sequential decision problems, based on an enumerated state space representation. More compact and structured representations have been proposed: factorization techniques use state variables representations, while decomposition techniques are based on a partition of the state space into sub-regions and take advantage of the resulting structure of the state transition graph. We use a family of probabilistic exploration-like...
Information flows, graphs and their guessing numbers.
Initial powers of Sturmian sequences
Integer partitions, tilings of -gons and lattices
In this paper, we study two kinds of combinatorial objects, generalized integer partitions and tilings of -gons (hexagons, octagons, decagons, etc.). We show that the sets of partitions, ordered with a simple dynamics, have the distributive lattice structure. Likewise, we show that the set of tilings of a -gon is the disjoint union of distributive lattices which we describe. We also discuss the special case of linear integer partitions, for which other dynamical models exist.
Integer Partitions, Tilings of 2D-gons and Lattices
In this paper, we study two kinds of combinatorial objects, generalized integer partitions and tilings of 2D-gons (hexagons, octagons, decagons, etc.). We show that the sets of partitions, ordered with a simple dynamics, have the distributive lattice structure. Likewise, we show that the set of tilings of a 2D-gon is the disjoint union of distributive lattices which we describe. We also discuss the special case of linear integer partitions, for which other dynamical models exist.
Integers in number systems with positive and negative quadratic Pisot base
We consider numeration systems with base β and − β, for quadratic Pisot numbers β and focus on comparing the combinatorial structure of the sets Zβ and Z− β of numbers with integer expansion in base β, resp. − β. Our main result is the comparison of languages of infinite words uβ and u− β coding the ordering of distances between consecutive β- and (− β)-integers. It turns out that for a class of roots β of x2 − mx − m, the languages coincide, while for other quadratic Pisot numbers the language...
Inverse problems of symbolic dynamics
This paper reviews some results regarding symbolic dynamics, correspondence between languages of dynamical systems and combinatorics. Sturmian sequences provide a pattern for investigation of one-dimensional systems, in particular interval exchange transformation. Rauzy graphs language can express many important combinatorial and some dynamical properties. In this case combinatorial properties are considered as being generated by a substitutional system, and dynamical properties are considered...
I/O-optimal algorithms for outerplanar graphs.
Iterative and metric algebraic theories
-colored point-set embeddability of outerplanar graphs.
Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde
Nous montrons que le tracé d’un kolam indien classique, que l’on retrouve aussi dans la tradition des dessins sur le sable aux îles Vanuatu, peut être engendré par un morphisme de monoïde. La suite infinie morphique ainsi obtenue est reliée à la célèbre suite de Prouhet-Thue-Morse, mais elle n’est -automatique pour aucun entier .