On December 13, 2022, Sang-il Oum of the IBS Discrete Mathematics Group received the Choi Seok-Jeong Award of the year (올해의 최석정상) from the Minister of Science and ICT of Korea. This is the 2nd year of this award named after Choi, Seok-jeong, known for discovering a pair orthogonal Latin squares of order 9 for the first time ahead of Euler.

## Sang-il Oum (엄상일) gave a talk at the Discrete Math Seminar on an explicit upper bound of the size of each obstruction for graphs of linear rank-width at most k and matroids of path-width at most k

On February 28, 2022, Sang-il Oum from IBS Discrete Mathematics Group and KAIST gave a talk at the Discrete Math Seminar on an explicit upper bound of the size of pivot-minor obstructions of graphs of linear rank-width at most k and the size of F-representable minor obstructions of matroids of path-width at most k. The title of his talk was “Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k“.

## Sang-il Oum (엄상일), Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field $\mathbb F$, the list contains only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these $\mathbb F$-representable excluded minors in general.

We consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field $\mathbb F$, every $\mathbb F$-representable excluded minor for the class of matroids of path-width at most~$k$ has at most $2^{|\mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute, for any integer $k$ and a fixed finite field $\mathbb F$, the set of $\mathbb F$-representable excluded minors for the class of matroids of path-width $k$, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an $\mathbb F$-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.

This is joint work with Mamadou M. Kanté, Eun Jung Kim, and O-joung Kwon.

## Sang-il Oum (엄상일) gave a talk on isotropic systems at the Discrete Math Seminar

On April 20, 2021, Sang-il Oum (엄상일) from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar introducing isotropic systems introduced by Bouchet in 1980s. The title of his talk was “What is an isotropic system?“.

## Sang-il Oum (엄상일), What is an isotropic system?

Bouchet introduced isotropic systems in 1983 unifying some combinatorial features of binary matroids and 4-regular graphs. The concept of isotropic system is a useful tool to study vertex-minors of graphs and yet it is not well known. I will give an introduction to isotropic systems.

## Sang-il Oum (엄상일), Survey on vertex-minors

For a vertex v of a graph G, the *local complementation* at v is an operation to obtain a new graph denoted by G*v from G such that two distinct vertices x, y are adjacent in G*v if and only if both x, y are neighbors of v and x, y are non-adjacent, or at least one of x, y is not a neighbor of v and x, y are adjacent. A graph H is a *vertex-minor* of a graph G if H is obtained from G by a sequence of local complementation and vertex deletions. Interestingly vertex-minors have been used in the study of measurement-based quantum computing on graph states.

Motivated by the big success of the graph minor structure theory developed deeply by Robertson and Seymour since 1980s, we propose a similar theory for vertex-minors. This talk will illustrate similarities between graph minors and graph vertex-minors and give a survey of known theorems and open problems on vertex-minors of graphs.

## Combinatorial and Discrete Optimization (2019 KSIAM Annual Meeting)

# Special Session @ 2019 KSIAM Annual Meeting

A special session on “Combinatorial and Discrete Optimization” at the 2019 KSIAM Annual Meeting is organized by Dabeen Lee. URL: https://www.ksiam.org/conference/84840fb6-87b0-4566-acc1-4802bde58fbd/welcome

## Date

**Nov 8, 2019** – **Nov 9, 2019** Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)

## Venue

Venezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔) Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)

## Speakers

**Hyung-Chan An (안형찬)**,*Yonsei University***Tony Huynh**,*Monash University***Dong Yeap Kang (강동엽)**,*KAIST / IBS Discrete Mathematics Group***Dabeen Lee (이다빈)**,*IBS Discrete Mathematics Group***Kangbok Lee (이강복)**,*POSTECH***Sang-il Oum (엄상일)**,*IBS Discrete Mathematics Group / KAIST***Kedong Yan**,*Nanjing University of Science and Technology***Se-Young Yun (윤세영)**,*KAIST*

## Schedules

- Combinatorial and Discrete Optimization I: November 8, 2019 Friday, 14:20 – 15:40.
- Kangbok Lee
- Kedong Yan
- Dabeen Lee
- Se-young Yun

- Combinatorial and Discrete Optimization II: November 9, 2019 Saturday, 10:00 – 11:20.
- Hyung Chan An
- Dong Yeap Kang
- Tony Huynh
- Sang-il Oum

## Abstracts

#### Kangbok Lee (이강복), Bi-criteria scheduling

#### Kedong Yan, Cliques for multi-term linearization of 0-1 multilinear program for boolean logical pattern generation

#### Dabeen Lee (이다빈), **Joint Chance-constrained programs and the intersection of mixing sets through a submodularity lens**

The intersection of mixing sets with common binary variables arise when modeling joint linear chance-constrained programs with random right-hand sides and finite sample space. In this talk, we first establish a strong and previously unrecognized connection of mixing sets to submodularity. This viewpoint enables us to unify and extend existing results on polyhedral structures of mixing sets. Then we study the intersection of mixing sets with common binary variables and also linking constraint lower bounding a linear function of the continuous variables. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull.

#### Se-Young Yun (윤세영), Optimal sampling and clustering algorithms in the stochastic block model

#### Hyung-Chan An (안형찬), Constant-factor approximation algorithms for parity-constrained facility location problems

*Facility location*is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather disturbing when we consider the central role of

*parity*in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of

*facilities*and

*clients*, the opening cost of each facility, and the

*parity requirement*—$\mathsf{odd}$, $\mathsf{even}$, or $\mathsf{unconstrained}$—of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a $T$-join on an auxiliary graph constructed by the algorithm. This graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and

*sparse*$T$-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. At the end of this paper, we also present the first constant-factor approximation algorithm for the parity-constrained $k$-center problem, the bottleneck optimization variant.

#### Dong Yeap Kang (강동엽), On minimal highly connected spanning subgraphs in dense digraphs

In 1985, Mader showed that every $n(\geq4k+3)$-vertex strongly $k$-connected digraph contains a spanning strongly $k$-connected subgraph with at most $2kn-2k^2$ edges, and the only extremal digraph is a complete bipartite digraph $DK_{k,n−k}$. Nevertheless, since the extremal graph is sparse, Bang-Jensen asked whether there exists g(k) such that every strongly $k$-connected $n$-vertex tournament contains a spanning strongly $k$-connected subgraph with $kn + g(k)$ edges, which is an “almost $k$-regular” subgraph.

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

#### Sang-il Oum, Rank-width: Algorithmic and structural results

## Sang-il Oum delivered the plenary lecture at the 2019 KMS Spring Meeting.

Sang-il Oum delivered the plenary lecture at the 2019 Korean Mathematical Society Spring Meeting (대한수학회 봄 연구발표회) held at the Kangwon National University in Chuncheon on April 19-20, 2019. The title of his talk was “How to decompose a graph into a tree-like structure”.