Tag: Team seminar
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 ...
Algorithms for the Metric Dimension problem on directed graphs
summary: In graph theory, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices, such that for any pair of vertices of the graph, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem ...
Complexity of positional games
summary: Positional games are two-player games played on a hypergraph. The players alternate selecting vertices of the hypergraph, and the winning conditions depend solely on the filling of the hyperedges. Tic-tac-toe is a famous example of a positional game, with the rows, columns, and diagonals forming the hyperedges and the ...
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 ...