Events

Title: Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

Abstract:

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field $\mathbb F$, the list contains only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)].

Title: “Lattice-Based Zero-Knowledge Arguments for Integer Relations” by Benoit Libert, San Ling, Khoa Nguyen, and Huaxiong Wang

Abstract:

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial size modulus q.

Title: Type B q-Stirling numbers

Abstract:

The Stirling numbers of the first and second kind are classical objects in enumerative combinatorics which count the number of permutations or set partitions with a given number of blocks or cycles, respectively. Carlitz and Gould introduced q-analogues of the Stirling numbers of the first and second kinds, which have been further studied by many authors including Gessel, Garsia, Remmel, Wilson, and others, particularly in relation to certain statistics on ordered set partitions.

Title: Strongly nonexpansive mappings revisited: uniform monotonicity and operator splitting

Abstract:

The correspondence between the class of nonexpansive mappings and the class of maximally monotone operators via the reflected resolvents of the latter has played an instrumental role in the convergence analysis of the splitting methods. Indeed, the performance of some of these methods, e.g., Douglas–Rachford and Peaceman–Rachford methods hinges on iterating the so-called splitting operator associated with the individual operators.

Title: On packing dijoins in digraphs and weighted digraphs

Abstract:

Let D=(V,A) be a digraph. A dicut is the set of arcs in a cut where all the arcs cross in the same direction, and a dijoin is a set of arcs whose contraction makes D strongly connected. It is known that every dicut and dijoin intersect. Suppose every dicut has size at least k.

Title: A Multijection of Cokernels

Absract:

I discovered an intriguing linear algebra relationship which I call a multijection. I used this construction to solve an open problem about higher-dimensional sandpile groups, but I think that it has more to say.

Title: Fixed-size schemes for certification of large quantum systems

Abstract:

In this talk I will introduce the concept of self-testing which aims to answer the fundamental question of how do we certify proper functioning of black-box quantum devices. We will see that there is a close link between self-testing and representations of algebraic relations. We will leverage this link to propose a family of protocols capable of certifying quantum states and measurements of arbitrarily large dimension with just four binary-outcome measurements.

This is a joint work with Chris Schafhauser and Jitendra Prakash.

Title: Decomposing graphs and hypergraphs into complete bipartite subgraphs

Abstract:

The problem of decomposing (partitioning or covering) graphs into complete bipartite subgraphs (bicliques) has a long history. In this talk, I will describe the basic results including the use of spectral methods, the extension of the problem to hypergraphs and present some of the open problems in this area.

Title: Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

Abstract:

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red.

Title: Sorting probabilities for Young diagrams and beyond

Abstract:

Sorting probability for a partially ordered set P is defined as the min |Pr[x<y] - Pr[y<x]| going over all pairs of elements x,y in P, where Pr[x<y] is the probability that in a uniformly random linear extension (extension to total order) x appears before y.

The celebrated 1/3-2/3 conjecture states that for every poset the sorting probability is at most 1/3, i.e. there are two elements x and y, such that 1/3\leq Pr[x<y] \leq 2/3.