# Past Events

## November 2019

### Speaker

Frédéric Meunier
École Nationale des Ponts et Chaussées, Paris
https://cermics.enpc.fr/~meuniefr/

Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb {R}$. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for the minrank parameter over $\mathbb {R}$ – an important graph invariant from coding theory – and show that this bound is actually valid for all…

Find out more »

## December 2019

### Speaker

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low…

Find out more »

### Speaker

Hong Liu
Mathematics Institute, University of Warwick, UK
http://homepages.warwick.ac.uk/staff/H.Liu.9/

Given any integers $s,t\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of…

Find out more »

### Speaker

Let ${\mathcal{M} = (M_i \colon i\in K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$. We prove the following Cantor-Bernstein-type result: if $E$ can be covered by sets ${(B_i \colon i\in K)}$ which are bases in the corresponding matroids and there are also pairwise disjoint bases of the matroids $M_i$ then $E$ can be partitioned into bases with respect to $\mathcal{M}$.

Find out more »

### Speaker

To an abelian category A satisfying certain finiteness conditions, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a non-additive setting, Dyckerhoff and Kapranov introduced the notion of proto-exact categories, as a non-additive generalization of an exact category, which is shown to suffice for the construction of an associative Hall algebra. In this talk, I will discuss the category of matroids in this perspective.

Find out more »

## January 2020

### Speaker

In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models such as random forests or support vector machines. In this talk, we consider boolean decision rule sets (equivalent to boolean functions in disjunctive normal form) as interpretable models for binary classification. We define the complexity of a rule set to be the number of rules (clauses) plus the number of…

Find out more »

### Speaker

Ben Lund
Princeton University
http://www.ben-lund.com

An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved by Dvir in 2008. Dvir's proof introduced the polynomial method to incidence geometry, which led to the solution to many long-standing problems in the area. I will talk about a generalization of the Kakeya conjecture posed by Ellenberg, Oberlin, and Tao. A $(k,m)$-Furstenberg set S in $\mathbb F_q^n$ has the property that,…

Find out more »

### Speaker

What is the largest subset of $Z_{2^n}$ that doesn't contain a projective d-cube? In the Boolean lattice, Sperner's, Erdos's, Kleitman's and Samotij's theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $Z_2^n$ we work in $Z_{2^n}$, analogous statements hold if one replaces the word k-chain by projective cube of dimension $2^{k-1}$. The largest d-cube-free subset of $Z_{2^n}$, if d is not a power of two, exhibits…

Find out more »

### Speaker

Dillon Mayhew
Victoria University of Wellington, New Zealand

Courcelle's Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic second-order logic of graphs, and as long as the input is restricted to a class of graphs with bounded tree-width. There are several properties that are NP-complete in general, but which can be expressed in monadic logic (3-colourability, Hamiltonicity...), so Courcelle's Theorem implies that these difficult properties…

Find out more »

## February 2020

### Speaker

Dong Yeap Kang (강동엽)
KAIST / IBS Discrete Mathematics Group
http://mathsci.kaist.ac.kr/~dykang/

We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases. We also discuss analogous results for randomly perturbed bipartite graphs as well as the size of a largest complete odd minor in randomly…

Find out more »
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr