Tag: Team seminar
Graph colourings, subcolourings, and beyond
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 ...
Games on Tilings
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
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
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
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 ...
Boolean dimension of boolean lattices
summary: Partially ordered sets (or posets for short) are structures that arise naturally in mathematics in the study of binary relations between objects. A poset consists of a ground set -- a set of elements -- and a partial order among them, and are usually visualled with directed acyclic graphs (DAGs). Indeed ...
Efficient maximal cliques enumeration in weakly closed graphs
summary: We show that the algorithm presented in [J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein. Finding cliques in social networks: A new distribution-free model. SIAM journal on computing, 49(2):448-464, 2020] can be modified to have enumeration time complexity αO(n·poly(c)). Here parameter ...
Auction mechanisms for allocation and pricing in Edge Computing
summary: Soon, billions of devices will be connected to the Internet, and most of them will need external resources to store and process their data. Edge Computing can benefit these devices by making these resources available at the network's edges to be closer to the user. However, these offered ...
A Closure Lemma for tough graphs and Hamiltonian degree conditions
summary: A graph G is Hamiltonian if there exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G−S is at most |S|/t. We extended the theorem of ...
Memory-Optimization for Self-Stabilizing Distributed Algorithms
summary: Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it ...