List of upcoming online seminars in discrete mathematics, combinatorics, and graph theory

Title: The precise diameter of reconfiguration graphs
by Stijn Cambie (IBS ECOPRO) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

Title: Transducing paths in graph classes with unbounded shrubdepth
by Sebastian Siebertz (University of Bremen) as part of IBS Virtual Discrete Math Colloquium

Abstract: TBA

by Richard Montgomery (Warwick) as part of Warwick Combinatorics Seminar

Interactive livestream: https://zoom.us/j/99265174877?pwd=Q3RSZVNxUWx5RGtYUGhOQ0wvd2pSdz09
Password hint: See webpage of the seminar.
Abstract: TBA

Title: Deep learning for sequence modelling
by Qianxiao Li as part of SMRI Seminar Series: Machine learning for the working mathematician

Lecture held in Carslaw 273 & Online.

Abstract
In this talk, we introduce some deep learning based approaches for modelling sequence to sequence relationships that are gaining popularity in many applied fields, such as time-series analysis, natural language processing, and data-driven science and engineering. We will also discuss some interesting mathematical issues underlying these methodologies, including approximation theory and optimization dynamics.

Title: Introsurvey of representation theory
by Nicolas Libedinsky (Universidad de Chile) as part of ARCSIN – Algebra, Representations, Combinatorics and Symmetric functions in INdia

Abstract
We will give a summary of the paper Introsurvey of representation theory. We will start with classical Schur-Weyl duality, then introduce Iwahori-Hecke algebra and Soergel bimodules. We will finish with some of the fascinating theorems and conjectures around these objects.

Title: Szeged workshop on convexity
by University of Szeged as part of Budapest Big Seminar on Combinatorics + Geometry

Interactive livestream: https://zoom.us/j/96029300722
Password hint: First six numbers in the Fibonacci sequence starting with 1 1
Abstract: TBA

by Hongseok Yang (KAIST) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

Title: Algorithmic Contract Theory
by Inbal Talgam-Cohen (Technion – Israel Institute of Technology) as part of TCS+

Abstract: TBA

Title: Abordagem da equipe Shadoks para partição mínima em subgrafos de plano
by Guilherme Fonseca (Aix-Marseille Université) as part of Seminário Brasileiro de Grafos, Algoritmos e Combinatória

Abstract: TBA

Title: Sums of linear transformations
by Jeck Lim (Caltech) as part of IBS Virtual Discrete Math Colloquium

Interactive livestream: https://us02web.zoom.us/j/87003129412?pwd=MWQzVmdKaVJueGNXbXJqNEVaM1l5dz09
Abstract: TBA

We show that if $L_1$ and $L_2$ are linear transformations from $\mathbb{Z}^d$ to $\mathbb{Z}^d$ satisfying certain mild conditions, then, for any finite subset $A$ of $\mathbb{Z}^d$,

$$|L_1 A+L_2 A|\geq (|\det(L_1)|^{1/d}+|\det(L_2)|^{1/d})^d |A|- o(|A|).$$

This result corrects and confirms the two-summand case of a conjecture of Bukh and is best possible up to the lower-order term for many choices of $L_1$ and $L_2$. As an application, we prove a lower bound for $|A + \lambda \cdot A|$ when $A$ is a finite set of real numbers and $\lambda$ is an algebraic number.

Joint work with David Conlon.

Title: Higher order Verma modules, and a positive formula for all highest weight modules – talk 2
by Apoorva Khare (Indian Institute of Science) as part of ARCSIN – Algebra, Representations, Combinatorics and Symmetric functions in INdia

Abstract
We study weights of highest weight modules $V$ over a Kac-Moody algebra $\mathfrak{g}$ (one may assume this to be $\mathfrak{sl}_n$ throughout the talk, without sacrificing novelty). To keep this talk self-contained, we begin by recalling the notation, higher order holes, and weight formulas for general $V$ from the previous lecture, along with some examples. We then define higher order Verma modules, and explain BGG resolutions and Weyl-Kac type character formulas for them in certain cases. (Joint with G.V.K. Teja.)

We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (A&C DN for short) which extends existential MSO1 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed A&C DN formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions.

Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (ETH) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the ETH for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-NP-hard when parameterized by mim-width plus formula length.

Joint work with Benjamin Bergougnoux and Jan Dreier.

Title: Caps and Probabilistic Methods
by Ferdinand Ihringer (Ghent University) as part of University of Regina math & stats colloquium

Lecture held in RI 208 (Research and Innovation Centre).

Abstract
A set of points in a finite projective space $\mathrm{PG}(n, q)$ with no three collinear is called a cap. More generally, a set of points in $\mathrm{PG}(n, q)$ such that no $s$-space contains more than $r$ points is called an $(r, s; n, q)$-set. In the first (and main) part of the talk we will discuss probabilisitic approaches to this classical problem.

In the second part of the talk, if time permits, we will discuss one reason why it is so hard to construct large caps. For this we present parameter restrictions on approximately strongly regular graphs. This is joint work with Jacques Verstraëte.

Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset
of a translation of the other. The comparable box dimension of a graph
$G$ is the minimum integer $d$ such that $G$ can be represented as a
touching graph of comparable axis-aligned boxes in $\mathbb{R}^d$. We
show that proper minor-closed classes have bounded comparable box
dimension and explore further properties of this notion. In particular we show that graphs with bounded comparable box dimension are treewidth fragile.

Joint work with Z. Dvořák, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

by Amadeus Reinald (TU Graz) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B232, IBS.
Abstract: TBA

Title: Independent sets in random subgraphs of the hypercube
by Gal Kronenberg (Oxford) as part of Warwick Combinatorics Seminar

Interactive livestream: https://zoom.us/j/99265174877?pwd=Q3RSZVNxUWx5RGtYUGhOQ0wvd2pSdz09
Password hint: See webpage of the seminar.

Abstract
Independent sets in bipartite regular graphs have been studied extensively in combinatorics, probability, computer science and more. The problem of counting independent sets is particularly interesting in the $d$-dimensional hypercube $\{0,1\}^d$, motivated by the lattice gas hardcore model from statistical physics. Independent sets also turn out to be very interesting in the context of random graphs.

The number of independent sets in the hypercube $\{0,1\}^d$ was estimated precisely by Korshunov and Sapozhenko in the 1980s and recently refined by Jenssen and Perkins.

In this talk we will discuss new results on the number of independent sets in a random subgraph of the hypercube. The results extend to the hardcore model and rely on an analysis of the antiferromagnetic Ising model on the hypercube.

This talk is based on joint work with Yinon Spinka.

We study the approximability of covering problems when the set of
items chosen to satisfy the covering constraints must be a prefix of a
given partial order. We examine the general case with multiplicity
constraints, where item $i$ can be chosen up to $d_i$ times. For the
basic Precedence-Constrained Knapsack problem (PCKP) we answer an open
question of McCormick et al. and show the existence of approximation
algorithms with strongly-polynomial bounds.

PCKP is a special case, with a single covering constraint, of a
Precedence-Constrained Covering Integer Program (PCCP). For a general
PCCP where the number of covering constraints is $m \geq 1,$ we show
that an algorithm of Pritchard and Chakrabarty for Covering Integer
Programs can be extended to yield an $f$-approximation, where $f$ is
the maximum number of variables with nonzero coefficients in a
covering constraint. This is nearly-optimal under standard
complexity-theoretic assumptions and rather surprisingly matches the
bound known for the problem without precedence constraints.

Joint work with Antonis Skarlatos.

by Eiichi Bannai (Kyushu University, Japan) as part of Combinatorics Today Series – ITB

Abstract: TBA

Title: Taming graphs with no large creatures and skinny ladders
by Lars Jaffke (Univ. of Bergen) as part of IBS Virtual Discrete Math Colloquium

Abstract: TBA

by Brendan McKay (ANU, Australia) as part of Combinatorics Today Series – ITB

Abstract: TBA

by Mieczyslaw Borowiecki (University of Zielona Góra, Poland) as part of Combinatorics Today Series – ITB

Abstract: TBA

by Linda Lesniak (Western Michigan University, USA) as part of Combinatorics Today Series – ITB

Abstract: TBA

by Akihiro Munemasa (Tohoku University, Japan) as part of Combinatorics Today Series – ITB

Abstract: TBA

by Nicholas Wormald (Monash University, Australia) as part of Combinatorics Today Series – ITB

Abstract: TBA

by Edy Tri Baskoro (Institut Teknologi Bandung, Indonesia) as part of Combinatorics Today Series – ITB

Abstract: TBA

by Sang-il Oum (Institute for Basic Science and KAIST, South Korea) as part of Combinatorics Today Series – ITB

Abstract: TBA

by Nicolas Trotignon (CNRS, LIP, ENS de Lyon, France) as part of Combinatorics Today Series – ITB

Abstract: TBA

by Csilla Bujtás (University of Ljubljana, Ljubljana, Slovenia) as part of Combinatorics Today Series – ITB

Abstract: TBA