## Events Search and Views Navigation

## November 2019

### Frédéric Meunier, Topological bounds for graph representations over any field

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 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 R – an important graph invariant from coding theory – and show that this bound is actually valid for all fields as…

Find out more »## December 2019

### Jakub Gajarský, First-order interpretations of bounded expansion classes

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 »### Attila Joó, Base partition for finitary-cofinitary matroid families

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 »## June 2020

### Seymour is Seventy

A conference honouring the seventieth birthday of Paul Seymour To be held in ENS de Lyon, France, June 15 - 19, 2020 Conference Website: https://dimag.ibs.re.kr/seymour70/ Sponsors: IBS Discrete Mathematics Group. LIP, ENS de Lyon, France. Department of Mathematics, Princeton University.

Find out more »