We say that a 0-1 matrix A contains another such matrix (pattern) P if P can be obtained from a submatrix of A by possibly changing a few 1 entries to 0. The main question of this theory is to estimate the maximal number of 1 entries in an n by n 0-1 matrix NOT containing a given pattern P. This question has very close connections to Turan type extremal graph theory and also to the Devenport-Schinzel theory of sequences. Results in the extremal theory of 0-1 matrices proved useful in attacking problems in far away fields as combinatorial geometry and the analysis of algorithms. This talk will concentrate on acyclic patterns and survey some old and recent results in the area and will also contain several open problems.

In this talk, we discuss the paper “Achieving Occam’s razor: Deep learning for optimal model reduction” by Botond B. Antal et.al., PLOS Computational Biology, 2024.

In this talk, we discuss the paper “Deep learning linking mechanistic models to single-cell transcriptomics data reveals transcriptional bursting in response to DNA damage” by Zhiwei Huang, et. al., bioRxiv, 2024.

We prove the following variant of Helly’s classical theorem for Hamming balls with a bounded radius. For $n > t$ and any (finite or infinite) set $X$, if in a family of Hamming balls of radius $t$ in $X$, every subfamily of at most $2^{t+1}$ balls have a common point, so do all members of the family. This is tight for all $|X| > 1$ and all $n > t$. The proof of the main result is based on a novel variant of the so-called dimension argument, which allows one to prove upper bounds that do not depend on the dimension of the ambient space. We also discuss several related questions and connections to problems and results in extremal finite set theory and graph theory. This is joint work with N. Alon and B. Sudakov.

An edge-colored graph $H$ is called rainbow if all of its edges are given distinct colors.  An edge-colored graph $G$ is then called rainbow $H$-free when no copy of $H$ in $G$ is rainbow.  With this, we define a graph $G$ to be rainbow $H$-saturated when there is some proper edge-coloring of $G$ which is rainbow $H$-free, but for every pair of non-adjacent vertices $x,y\in V(G)$, the graph $G+xy$ formed by adding the edge $xy$ to $G$ cannot be given a rainbow $H$-free coloring.  We think of these graphs as edge-maximal rainbow $H$-free graphs.  (We note that here we make no restrictions on the colorings of $G+xy$ whatsoever, except that they are proper colorings.  They may use any number of colors, and need not be extensions of the original rainbow $H$-free coloring of $G$.) With this framework in place, we define the rainbow saturation number and rainbow extremal number to be the largest and smallest number of edges, respectively, among all $n$ vertex rainbow $H$-saturated graphs.  The latter of these was defined by Keevash, Mubayi, Sudakov, and Verstraëte in 2007; the former was introduced by B., Johnston, and Rombach in 2019.  In this talk, we discuss recent progress on both the rainbow saturation numbers and rainbow extremal numbers.  We also give several broad generalizations of these concepts and discuss many open problems.  This talk contains joint work with Vic Bednar (Furman), Dan Johnston (Trinity College, CT), and Puck Rombach (Vermont).

The realization that microbiomes, associated with virtually all multicellular organisms, have tremendous impact on their host health is considered as one of the most important scientific discoveries in the last decade. The host associated microbiomes, composed of tens to hundreds of co-existing microbial species, are highly heterogenous at multiple scales (e.g. between different hosts and within a host). In this talk, I will share our recent works on understanding the heterogeneity of complex microbial communities, and how these conceptual and technological advances in microbial ecology pave the way for precision microbiome engineering to prevent and treat diseases.

In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{k^2}{2} – \frac{k}{2} + 1$ by Addario-Berry et al. In this talk, we give the first subquadratic bound for Burr’s conjecture, by showing that every directed graph with chromatic number $8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)$ contains any oriented tree of order $k$. Moreover, we provide improved bounds of $\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)$ for arborescences, and $(b-1)(k-3)+3$ for paths on $b$ blocks, with $b\ge 2$.

Every (finite) matroid consists of a (finite) set called the ground set, and a collection of distinguished subsets called the independent sets. A classic example arises when the ground set is a finite set of vectors from a vector space, and the independent subsets are exactly the subsets that are linearly independent. Any such matroid is said to be representable. We can think of a representable matroid as being a geometrical configuration where the points have been given coordinates from a field. Another important class arises when the points are given coordinates from a group. Such a class is said to be gain-graphic. Monadic second-order logic is a natural language for matroid applications. In this language we are able to quantify only over subsets of the ground set. The importance of monadic second-order logic comes from its connections to the theory of computation, as exemplified by Courcelle’s Theorem. This theorem provides polynomial-time algorithms for recognising properties defined in monadic second-order logic (as long as we impose a bound on the structural complexity of the input objects). It is natural to ask which classes of matroids can be defined by sentences in monadic second-order logic. When the class consists of the matroids that are coordinatized by a field we have a complete answer to this question. When the class is coordinatized by a group the problem becomes much harder. This talk will contain a brief introduction to matroids. Based on work with Sapir Ben-Shahar, Matt Conder, Daryl Funk, Angus Matthews, Mike Newman, and Gabriel Verret.

For the past few years, I’ve been working on formalizing proofs in matroid theory using the Lean proof assistant. This has led me to many interesting and unexpected places. I’ll talk about what formalization looks like in practice from the perspective of a combinatorialist.

Depth and width parameters of graphs, e.g., tree-width, path-width and tree-depth, play a crucial role in algorithmic and structural graph theory. These notions are of fundamental importance in the theory of graph minors, fixed parameter complexity and the theory of sparsity. In this talk, we will survey structural and algorithmic results that concern width and depth parameters of matroids. We will particularly focus on matroid depth parameters and discuss the relation of the presented concepts to discrete optimization. As an application, we will present matroid based algorithms that uncover a hidden Dantzig-Wolfe-like structure of an input instance (if such structure is present) and transform instances of integer programming to equivalent ones, which are amenable to the existing tools in integer programming. The most recent results presented in the talk are based on joint work with Marcin Briański, Jacob Cooper, Timothy F. N. Chan, Martin Koutecký, Ander Lamaison, Kristýna Pekárková and Felix Schröder.