## Archive for the ‘KAIST Discrete Math Seminar’ Category

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

Monday, October 28th, 2019

IBS/KAIST Joint Discrete Math Seminar

Topological bounds for graph representations over any field
Frédéric Meunier
École Nationale des Ponts et Chaussées, Paris
2019/11/21 Thu 4:30PM-5:30PM, Room B232, IBS (기초과학연구원)
ABSTRACT

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 well. The notion of independent representation over a matroid is introduced and used in a general theorem having these results as corollaries. Related complexity results are also discussed.
This is joint work with Meysam Alishahi.

### Pascal Gollin, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs

Sunday, October 27th, 2019

IBS/KAIST Joint Discrete Math Seminar

A Cantor-Bernstein-type theorem for spanning trees in infinite graphs
Pascal Gollin
IBS Discrete Mathematics Group
2019/10/29 Tue 4:30PM-5:30PM Room B232, IBS (기초과학연구원)
Given a cardinal $\lambda$, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$, and a $\lambda$-covering of $G$ is a family of spanning trees covering $E(G)$.

We show that if a graph admits a $\lambda$-packing and a $\lambda$-covering  then the graph also admits a decomposition into $\lambda$ many spanning trees. In this talk, we concentrate on the case of $\lambda$ being an infinite cardinal. Moreover, we will provide a new and simple proof for a theorem of Laviolette characterising the existence of a $\lambda$-packing, as well as for a theorem of Erdős and Hajnal characterising the existence of a $\lambda$-covering.

Joint work with Joshua Erde, Attila Joó, Paul Knappe and Max Pitz.

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

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

First-order interpretations of bounded expansion classes
Jakub Gajarský
Technische Universität Berlin
2019/12/10 Tue 4:30PM-5:30PM (Room B232, IBS)
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 treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

### Ruth Luo, Induced Turán problems for hypergraphs

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

Induced Turán problems for hypergraphs
Ruth Luo
University of California, San Diego
2019/11/19 Tue 4:30PM-5:30PM (Room B232, IBS)
Let $F$ be a graph. We say that a hypergraph $\mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $\mathcal H$ such that for all $xy \in E(F)$, $f(xy) \cap V(F) = \{x,y\}$. In this talk, we show asymptotics for the maximum number of edges in $r$-uniform hypergraphs with no induced Berge $F$. In particular, this function is strongly related to the generalized Turán function $ex(n,K_r, F)$, i.e., the maximum number of cliques of size $r$ in $n$-vertex, $F$-free graphs.  Joint work with Zoltan Füredi.

### Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

Stable sets in graphs with bounded odd cycle packing number
Tony Huynh
Monash University
2019/11/12 Tue 4:30PM-5:30PM (Room B232, IBS)
It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$.  We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$.  Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface. Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which we prove to be efficiently solvable in our case. This is joint work with Michele Conforti, Samuel Fiorini, Gwenaël Joret, and Stefan Weltge.