Tag: Team seminar
Faster diameter computation in graphs of bounded Euler genus
Roditty and Vassilevska-Williams [STOC 2013] showed that computing the diameter, i.e., farthest distance between any two vertices, of an (unweighted, undirected) graph cannot be done in subquadratic time unless the Strong Exponential Time Hypothesis fails. In a breakthrough work, Cabello [TALG 2019] showed a subquadratic algorithm in planar graphs ...
Les méandres arcs-en-ciel sur des chemins de Dyck
Un méandre (de longueur n) est une paire de correspondences non-croisées sur {1,...,n}. On peut le représenter sur le plan réel comme un paire d'ensemble de demi-cercles, qui ne s'intersentent pas deux à deux, reliant n points sur une droite. Cette représentation géométrique permet d'introduire différentes ...
Lattice structures of Gog and Magog triangles
summary:
Gog and Magog triangles are simple combinatorial objects which are equienumerated.
Howewer, the problem of finding an explicit bijection between these has been an
open problem since the 80’s. These are related to other interesting objects such
as alternating sign matrices, plane partitions or aztec diamond tillings.
All ...
Non-intersecting paths and the determinant of the distance matrix of a tree
summary:
We present a combinatorial proof of the Graham–Pollak formula for the determinant of the
distance matrix of a tree, via sign-reversing involutions and the Lindström–Gessel–Viennot Lemma.
This is joint work with Emmanuel Briand, Luis Esquivias-Quintero, Álvaro Gutierrez, and Adrián Lillo.
Une nouvelle description des treillis m-cambriens
summary:
Les treillis cambriens, introduits par N. Reading en 2006, sont une généralisation du treillis de Tamari, à tout choix d'élément de Coxeter, dans tout groupe de Coxeter fini. Le treillis de Tamari correspond au "type A linéaire". Ces ordres partiels admettent plusieurs descriptions, non trivialement équivalentes. Celles-ci donnent ...Proper conflict-free colourings of graphs
summary: Given a graph \(G\) of maximum degree \(\Delta\), the proper colouring problem asks for the minimum number of colours that can be assigned to the vertices of \(G\) such that no pair of adjacent vertices are given the same colour; it is easy to show that at most \(\Delta ...
Alternating and nondeterministic plane-walking automata
summary: Plane-walking automata were introduced by Salo & Törma to recognise languages of two-dimensional infinite words (subshifts), the counterpart of 4-way finite automata for two-dimensional finite words. We extend the model to allow for nondeterminism and alternation of quantifiers. We prove that the recognised subshifts form a strict subclass of sofic ...
On the complexity of computing tree-partitions
summary: Tree-partitions are graph decompositions that correspond to mapping vertices to nodes of a tree in such a way that adjacent vertices in the graph are either mapped to adjacent nodes of the tree or to the same node. The width of a tree-partition is the maximum number of vertices ...
On the intervals of framing lattices
summary: A flow graph \(G\) is an acyclic oriented graph with \(V(G) = [n]\), \(E(G)\) a multi-set of edges where each edge \((i,j)\) satisfies \(i<j\), and such that \(G\) has a unique source \(s=1\) and sink \(t=n\). On such a graph, a route is simply ...
On the Structure of Potential Counterexamples to the Borodin-Kostochka Conjecture
summary: The Borodin-Kostochka conjecture, a long-standing problem in graph theory, asserts that every graph \(G\) with maximum degree \(\Delta \geq 9\) satisfies \(\chi(G) \leq max \{\Delta - 1, \omega(G)\}\) where \(\chi(G)\) and \(\omega(G)\) are respectively the chromatic number and the clique number of \(G\). While the conjecture ...
Page 1 / 12 »