It is a common strategy to solve efficiently NP-complete problems on graphs by exploiting one of its adventageous structural parameters. This approach has led to the very potent theory of parameterized complexity, in which some parameters such as treewidth or cliquewidth have emerged as especially efficient to design fast parameterized algorithms.

Following the same principle, Bonnet et al. have very recently introduced the notion of contraction sequence of a graph: the high-level idea is to gain time by treating similarily vertices with a similar neighborhood, generalizing naturally the algorithms on cographs.

The quality of a contraction sequence can be mesured by two (among other) non-functionally equivalent parameters called twin-width and component twin-width. It is clear that the primary focus of Bonnet et al. was twin-width, leaving component twin-width almost unexplored in the whole literature.

It is known that cliquewidth and component twinwidth are functionnaly equivalent: Bonnet et al. proved this result through functional equivalence with booleanwidth (which is known to be functionnaly equivalent with cliquewidth), which leads to an exponential bound on component twin-width by cliquewidth; and a double-exponential bound on cliquewidth by component twin-width.

In this presentation, I will prove that these two bounds can be drastically improved: we will obtain very simple linear bounds. Then, I will give an example of a concrete application of component twin-width (using dynamic programming) that always beats the best known upper bounds of the complexity of a counting version of several graph coloring problems. Finally, I will discuss how the linear bounds obtained can be used to extend the results known on the approximations of cliquewidth to approximations of component twinwidth.

A proper k-vertex coloring of a digraph D is a mapping $c:V(D) \rightarrow \{1,\cdots,k}$ such that no two adjacent vertices are assigned the same color. In this case we say that D is k-colorable. The minimum k for which a digraph D is k-colorable is called the chromatic number of D. How does the chromatic number of a digraph relate to other digraph's invariants, such as connectivity, girth and subdigraphs?

During this talk we are going to present how the existence of certain types of paths and cycles in a digraph affects its chromatic number.

Each hereditary property can be characterized by its set of minimal obstructions; these sets are often unknown, or known but infinite. By allowing extra structure it is sometimes possible to describe such properties by a finite set of forbidden objects. This has been studied most intensely when the extra structure is a linear ordering of the vertex set. For instance, it is known that a graph G is $k$-colourable if and only if $V(G)$ admits a linear ordering $\le$ with no vertices $v_1 \le \cdots \le v_{k+1}$ such that $v_iv_{i+1} \in E(G)$ for every $i \in \{ 1, \dots, k \}$. In this talk, we have a look at such characterizations when the extra structure is a circular ordering of the vertex set. In particular, we show that the classes that can be described by finitely many forbidden circularly ordered graphs include forests, circular-arc graphs, and graphs with circular chromatic number (strictly) less than $k$.

Nowhere-zero flows of unsigned graphs were introduced by Tutte in 1954 as a dual problem to vertex-coloring of (unsigned) planar graphs. The definition of nowhere-zero flows on signed graphs naturally comes from the study of embeddings of graphs in non-orientable surfaces, where nowhere-zero flows emerge as the dual notion to local tensions. Nowhere-zero flows in signed graphs were introduced by Edmonds and Johnson in 1970 for expressing algorithms on matchings, but systematically studied first by Bouchet in 1983. Bouchet also stated a conjecture which occupies a central place in the area of signed graphs: Every flow-admissible signed graph admits a nowhere-zero 6-flow. There is a significant difference in the flows of signed graphs and unsigned graphs. In this talk I will talk about the progress on the development of the flow theory of signed graphs.

Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for a positive integer $k$, we seek a vertex ordering such every vertex can (weakly respectively strongly) reach in $k$ steps only few vertices that precede it in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in the structural and algorithmic graph theory. Recently, Dvo\v{r}\'ak, McCarty, and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in $\mathbb{R}^d$, such as homothets of a compact convex object, or comparable axis-aligned boxes.

In this paper, we prove upper and lower bounds for the $k$-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in $k$, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).

This is joint work with Zden\v{e}k Dvo\v{r}\'{a}k, Jakub Pek\'arek and Torsten Ueckerdt.

The lottery ticket hypothesis states that a randomly-initialized neural network contains a small subnetwork which, when trained in isolation, can compete with the performance of the original network. Recent theoretical works proved an even stronger version: every sufficiently overparameterized (dense) neural network contains a subnetwork that, even without training, achieves accuracy comparable to that of the trained large network.These works left as an open problem to extend the result to convolutional neural networks (CNNs). In this work we provide such generalization by showing that, with high probability, it is possible to approximate any CNN by pruning a random CNN whose size is larger by a logarithmic factor.

We revisit the planning problem in the blocks world, and we implement a known heuristic for this task. Importantly, our implementation is biologically plausible, in the sense that it is carried out exclusively through the spiking of neurons. Even though much has been accomplished in the blocks world over the past five decades, we believe that this is the first algorithm of its kind. The input is a sequence of symbols encoding an initial set of block stacks as well as a target set, and the output is a sequence of motion commands such as “put the top block in stack 1 on the table”. The program is written in the Assembly Calculus, a recently proposed computational framework meant to model computation in the brain by bridging the gap between neural activity and cognitive function. Its elementary objects are assemblies of neurons (stable sets of neurons whose simultaneous firing signifies that the subject is thinking of an object, concept, word, etc.), its commands include project and merge, and its execution model is based on widely accepted tenets of neuroscience. A program in this framework essentially sets up a dynamical system of neurons and synapses that eventually, with high probability, accomplishes the task. The purpose of this work is to establish empirically that reasonably large programs in the Assembly Calculus can execute correctly and reliably; and that rather realistic – if idealized – higher cognitive functions, such as planning in the blocks world, can be implemented successfully by such programs. This is a joint work with Francesco d'Amore, Daniel Mitropolsky, Emanuele Natale, and Christos H. Papadimitriou.