(Reported to unkwown date) The Bron-Kerbosch algorithm with vertex ordering is output sensitive.

-- George Manoussakis (University of Versailles)

summary: The Bron-Kerbosch algorithm is a well known maximal clique enumeration algorithm. So far it was unknown whether it was output sensitive or not. In this paper we partially answer this question by proving that the Bron-Kerbosch Algorithm with vertex ordering, first introduced and studied by Eppstein, Löffler and Strash ...

Three interacting families of Fuss-Catalan posets

-- Camille Combe (IRMA, Strasbourg)

We will introduce three families of posets depending on a nonnegative integer parameter \(m\), having underlying sets enumerated by the \(m\)-Fuss Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. We will see how these three families of ...

L-orientations of graphs

-- Kenta Ozeki (Yokohama National University)

summary: An orientation of an (undirected) graph G is an assignment of directions to each edge of G. In this talk, we consider an orientation such that the out-degree of each vertex is contained in a given list. We introduce several relations to graph theory topics and pose our main ...

Formes limites de permutations à motifs interdits

-- Adeline Pierrot (LRI, Université Paris Saclay)

On s'intéresse aux ensembles de permutations à motifs exclus, appelés classes de permutations, qui ont été beaucoup étudiés en combinatoire énumérative. Dans ce travail, à la frontière entre combinatoire et probabilités, on s'intéresse à la limite d'échelle d'une grande permutation aléatoire uniforme dans une classe de ...

PHD defense: A guide book for the traveller on graphs full of blockages

-- Pierre Bergé (LRI, University of Paris Saclay)

summary: We study NP-hard problems dealing with graphs containing blockages.

We analyze cut problems via the parameterized complexity framework. The size p of the cut is the parameter. Given a set of sources {s_1,...,s_k} and a target t, we propose an algorithm deciding whether a cut of size at ...

Cardinal d'un ensemble de coupure minimal en percolation de premier passage

-- Marie Théret (Université Paris Nanterre)

On considère le modèle de percolation de premier passage sur \(\mathbb{Z}^d\) en dimension \(d\geq 2\) : on associe aux arêtes du graphe une famille de variables i.i.d. positives ou nulles. On interprète la variable aléatoire associée à une arête comme étant sa capacité, i.e., la ...

Optimal curing policy for epidemic spreading over a community network with heterogeneous population

-- Francesco De Pellegrini (University of Avignon)

summary: The design of an efficient curing policy, able to stem an epidemic process at an affordable cost, has to account for the structure of the population contact network supporting the contagious process. Thus, we tackle the problem of allocating recovery resources among the population, at the lowest cost possible ...

Permutahedral matchings, zonotopal tilings, and d-partitions

-- Cesar Ceballos

In this talk I will present higher dimensional generalizations of the following three concepts:

  • (a) perfect matchings of a hexagonal tiling,
  • (b) rhombus tilings of a hexagon, and
  • (c) plane partitions.

I will show that these generalizations are equivalent under certain specific bijections. The generalizations of (b) and (c) have ...

Brauer-Thrall Conjectures, Old and New!

-- Kaveh Mousavand

\(\tau\)-tilting theory is an elegant-- but technical-- subject in representation theory of associative algebras, with motivations from cluster algebras. It was introduced by Adachi-Iyama-Reiten, in 2014. However, thanks to the recent result of Demonet-Iyama-Jasso, one can fully phrase the concept of \(\tau\)-tilting finiteness in terms of linear algebra ...

Geometry of random permutation factorizations

-- Paul Thevenin (CMAP, École Polytechnique)

We study random minimal factorizations of the \(n\)-cycle into transpositions, that is, factorizations of the cycle \((1 2...n)\) into a product of \(n-1\) transpositions. It is known that these factorizations are in bijection with Cayley trees of size \(n\), and therefore that there are \(n^{n-2}\) of them ...

Page 1 / 13 »