Tag: Team seminar
The Domino Snake Problem
summary: Deep within the swamp of undecidability lies the elusive domino snake. This species, first discovered in the 1970s by Myers, was originally introduced as an a priori simpler problem than the now celebrated Domino Problem. In this talk we will take a tour through what is known about this ...
The fixed-point construction in tilings
summary: Consider a tileset, i.e. a finite set of colors along with some adjacency constraints between them. It defines the set of colorings of the infinite grid that respects these adjacency constraints. Such a coloring is called a tiling. Given a tileset as input, a question naturally arises: does ...
Lattice properties of acyclic pipe dreams
summary: Pipe dreams were introduced by Bergeron and Billey in order to study Schubert polynomials and encode the algebraic structure of the symmetric group. In particular, with well-chosen parameters, they have the combinatorial structure of the Tamari lattice, a well-known quotient of the weak order on permutations. In this presentation ...
Proper vertex coloring with odd occurrence - Probabilistic approach
summary: In graph theory, a graph coloring is an assignment of colors to elements of a graph subject to certain constraints. A vertex coloring is said to be proper if any pair of two adjacent vertices are assigned distinct colors. For a graph G, the chromatic number χ(G) is ...
Some results on directed coloring
summary: Proper coloring of undirected graphs lies among the most studied
problems in graph theory. It asks to color vertices while giving
different colors to adjacent ones.
In 1982, Neumann-Lara introduced a generalization of this problem to
directed graphs. When walking in an undirected graph, an undirected edge
between two ...
Walking On A Line: finding S-adic walks in an ω-automaton
summary: At the heart of symbolic dynamics lies the study of languages, infinite words and the dynamical structures associated. We focus on two classical methods to generate such structures. The first one relies on substitutions, which are morphisms on words, by iterating one on an initial letter, and considering the ...
Realizing Geometrically s-Permutahedra via Flow Polytopes
summary: In 2020, Ceballos and Pons defined s-decreasing trees with s being a weak composition. They described an order on these objects called the s-weak order which gives them the order structure of a lattice. They further conjectured that this structure could be realized geometrically as the 1-skeleton of a ...
Density of sphere packings: from coins to oranges
summary: How to stack an infinite number of oranges to maximize the proportion of the covered space? Kepler conjectured that the "cannonball" packing is an optimal way to do it. This conjecture took almost 400 years to prove and the proof of Hales and Ferguson consists of 6 papers and ...
An introduction to twin-width in graphs via the study of highly inapproximable problems
summary: The goal of this seminar is to introduce the graph parameter "twin-width", defined by Bonnet et al. in 2020. The collection of graphs with bounded twin-width generalizes many well-known families of graphs : planar, bounded treewidth and cliquewidth, unit interval,... The first motivation behind this parameter was that FO-expressible NP-hard ...
TracInAD: Measuring Influence for Anomaly Detection
summary: As with many other tasks, neural networks prove very effective for anomaly detection purposes. However, very few deep-learning models are suited for detecting anomalies on tabular datasets. This talk proposes a novel methodology to flag anomalies based on TracIn, an influence measure initially introduced for explicability purposes. The proposed ...