## July 2021

### Jaehoon Kim (김재훈), $K_{r+1}$-saturated graphs with small spectral radius

Room B232 IBS (기초과학연구원)

For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e\in E(\overline G)$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a

### Semin Yoo (유세민), Combinatorics of Euclidean spaces over finite fields

Room B232 IBS (기초과학연구원)

$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues of binomial coefficients, denoted by $\binom{n}{k}_{q}$, which give the number of $k$-dimensional subspaces in $\mathbb{F}_{q}^{n}$. When $q$ goes to $1$, this reverts to the binomial

### Euiwoong Lee (이의웅), The Karger-Stein algorithm is optimal for k-cut

Room B232 IBS (기초과학연구원)

In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with

## August 2021

### Duksang Lee (이덕상), Intertwining connectivities for vertex-minors and pivot-minors

Room B232 IBS (기초과학연구원)

We show that for pairs (Q,R) and (S,T) of disjoint subsets of vertices of a graph G, if G is sufficiently large, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such that there are two ways to reduce G by a vertex-minor operation while preserving the connectivity between Q and R and the connectivity between S

### Linda Cook, Two results on graphs with holes of restricted lengths

Room B232 IBS (기초과학연구원)

We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain

### Eun Jung Kim (김은정), A Constant-factor Approximation for Weighted Bond Cover

Room B232 IBS (기초과학연구원)

The Weighted $\mathcal F$-Vertex Deletion for a class $\mathcal F$ of graphs asks, given a weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in\mathcal F$. The case when $\mathcal F$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal ### Cheolwon Heo (허철원), Representations of even-cycle matroids Room B232 IBS (기초과학연구원) A signed graph is a pair$(G,\Sigma)$where$G$is a graph and$\Sigma$is a subset of edges of$G$. A cycle$C$of$G$is a subset of edges of$G$such that every vertex of the subgraph of$G$induced by$C$has an even degree. We say that$C$is even ## September 2021 ### Dabeen Lee (이다빈), Mixing sets, submodularity, and chance-constrained optimization Room B232 IBS (기초과학연구원) A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this talk, we first explain basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we ### Kevin Hendrey, Extremal functions for sparse minors Room B232 IBS (기초과학연구원) The extremal function$c(H)$of a graph$H$is the supremum of densities of graphs not containing$H$as a minor, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) ## October 2021 ### Eunjin Oh (오은진), Feedback Vertex Set on Geometric Intersection Graphs Room B232 IBS (기초과학연구원) I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time$2^{O(\sqrt{k})}(n + m)$, where$n$and$m$denote the numbers of vertices and edges, respectively. This improves the$2^{O(\sqrt{k}\log k)}(n + m)\$-time algorithm for this problem on unit disk

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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, Fax: +82-42-878-9209