Category: seminars

Beyond the fractional Reed bound for triangle-free graphs

-- Tianjiao Dai (LISN, Galac)

summary: The notion of fractional colouring is an important concept in graph theory that is commonly used to extend the notion of graph colouring beyond integer values. It is a relaxation of the traditional chromatic number, allowing for real-valued weights or probabilities associated with each independent set of a graph ...

The Domino problem on rhombus-shaped tiles.

-- Benjamin Hellouin de Menibus (LISN, Galac)

summary: The word tiling is a name for several models: geometrical tilings, where you tile the plane with geometrical shapes like a jigsaw puzzle; and symbolic tilings, where you tile the plane while matching colors on the edges of tiles. You can use both kinds of constraints; a well-known example ...

Une généralisation de la correspondance RSK via des représentations de carquois (de type A)

-- Benjamin Dequene (UQAM)

La correpondance de Robinson-Schensted-Knuth est une bijection partant des matrices d'entiers naturels vers les paires de tableaux de Young semi-standards. Une version généralisée donne une bijection entre des remplissages d'un tableau d'une certaine forme, et les partitions planes renversés de la même forme.

D'un point de ...

Quantifiying the robustness of dynamical systems: relating time and space to length and precision

-- Manon Blanc (LISN, Galac)

summary: Reasoning about dynamical systems evolving over the reals is well-known to lead to undecidability. In particular, it is known there cannot be decision procedures for first-order theories over the reals, or decision procedures for state reachability. However, various results in the literature have shown that decision procedures exist when ...

Graph colourings, subcolourings, and beyond

-- Quentin Chuet (LISN, Galac)

summary: The graph colouring problem is central in Graph Theory: it consists in colouring the vertices of a graph such that each colour class induces an independent set, using as few colours as possible. While very difficult to solve exactly, the problem and its worst cases are now understood quite ...

Column-convex {0,1}-matrices, consecutive coordinate polytopes and flow polytopes

-- Rafael S. González D'León (Loyola univ. Chicago) (LIX)

We study normalized volumes of a family of polytopes associated with column-convex {0,1}-matrices. Such a family is a generalization of the family of consecutive coordinate polytopes, studied by Ayyer, Josuat-Vergès, and Ramassamy, which in turn generalizes a family of polytopes originally proposed by Stanley in EC1. We prove ...

Games on Tilings

-- Rémi Pallen (LISN, Galac)

summary: Given a finite set A of colors and a finite set of target
patterns F, to know if one can tile the infinite grid avoiding
patterns in F is the domino problem. This problem can be seen as a
one-player game, where the goal for the player is to ...

The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture.:00

-- Ugo Gioccanti (G-SCOP (Grenoble))

summary: An infinite graph is quasi-transitive if its automorphism group has finitely many orbits. In this talk, I will present a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. We prove that every locally finite quasi-transitive graph G ...

Modular Automata Networks

-- Pacôme Perrotin (LISN, Galac)

summary: Automata networks are finite dynamical systems used to model gene regulatory networks. In this talk we talk about the difficult task of characterizing their limit behavior, and explore the formalism of modules which aims to simplify some of the technicalities related to those tasks.

A simple counting argument applied to lower bounds on the growth of subshifts

-- Matthieu Rosenfeld (LIRMM (Montpellier))

summary: Given a group G, a set of colors A and a set of forbidden patterns F, the subshift X_F is the set of colorings of G by A that avoid the patterns in F. I recently obtained a simple condition on the set of forbidden patterns F that implies ...

« Page 3 / 23 »