Tag: Team seminar

Transversals in a collection of graphs with degree conditions

-- Hugo Demaret (LISN, Galac)

summary: Let G={G_1, G_2, ... , G_m} be a collection of n-vertex graphs on the same vertex set V (a graph system), and F be a simple graph with e(F) ≤ m. If there is an injection f: E(F) → [m] such that e &isinv E(G_{f(e)}) for each ...

Compact local certification of MSO properties for several tree-like parameters

-- Hugo Demaret (LISN, Galac)

summary: Local certification is interested in assigning labels (called certificates) to the vertices of a graph, in order to certify a certain property about said graph, or the correctness of a data-structure distributed on the graph. For the verification to be local, a vertex may only "see" its neighbourhood. A ...

Complexité du problème de distance d’édition minimum à un line-digraphe

-- Quentin Japhet (LISN, Galac)

summary: La distance d'édition est une mesure classique utilisée pour évaluer la proximité entre un graphe donné et un autre graphe ou une classe de graphes. Cette distance représente le nombre minimum de modifications requises pour transformer le graphe initial en un graphe appartenant à la classe voulue. Une ...

Skipless chain decompositions and improved poset saturation bounds

-- Paul Bastide (LaBRI (Bordeaux))

summary: We show that given m disjoint chains in the Boolean lattice, we can create m disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer ...

Asymptotic behaviour of cyclic automata

-- Benjamin Hellouin de Menibus (LISN, Galac)

summary: Cyclic dominance describes models where different states (species, strategies...) are in some cyclic prey-predator relationship: for example, rock-paper-scissors. This occurs in many contexts such as ecological systems, evolutionary games on graphs, etc. Many models exhibit heteroclinic cycles where one state dominates almost the whole space before being replaced by ...

La boîte aux lettres avait des dents : propriétés des pièges à facteurs dans le cas bi-infini

-- Pierre Béaur (LISN, Galac)

summary: En 2017, en algorithmique de texte, Prezza a introduit la notion de piège à facteurs : pour un mot fini w, un piège à facteurs pour w est un ensemble E de positions de w telles que pour tout facteur f de w, il existe une position de E qui ...

Complexity of neural network training and complexity proofs bypassing frontier issues

-- Valentin Dardilhac (LISN, Galac)

summary: We study the complexity of the neural network training decision
problem in two different contexts. First, in the general context, this
problem has been shown to be in extensions of the class ∃R. We have
been able to show that whenever the activation functions are Lipschitz
functions and the ...

Étude énumérative des intervalles dans les treillis de type Tamari

-- Clément Chenevière (LISN, Galac)

summary: Le treillis de Tamari est un ordre partiel sur les objets Catalan. De nombreuses descriptions de ce treillis donnent lieu à de nombreuses familles de généralisations, notamment les treillis m-Tamari, nu-Tamari et m-Cambriens. Après une "visite guidée" dans ce zoo des généralisations du treillis de Tamari, je présenterai mon ...

Edge k-q-colorability of graphs

-- Selma Djelloul (LISN, Galac)

summary: Given positive integers k, q, we say that a graph is edge k-q-colorable if its edges can be colored in such a way that the number of colors incident to each vertex is at most q and that the size of a largest color class is at most k ...

The freezing threshold for uniformly random colourings of sparse graphs

-- François Pirot (LISN, Galac)

summary: Given a random Δ-regular graph G, it holds that χ(G) ~ Δ / (2 ln Δ) with high probability. However, for any ε > 0 and k large enough, no (randomised) polynomial-time algorithm returning a proper k-colouring of such a random graph G is known to exist when k < (1−ε ...

Page 1 / 9 »