## July 2021

### Suil O (오수일), Eigenvalues and [a, b]-factors in regular graphs

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

For positive integers, $r \ge 3, h \ge 1,$ and $k \ge 1$, Bollobás, Saito, and Wormald proved some sufficient conditions for an $h$-edge-connected $r$-regular graph to have a k-factor in 1985. Lu gave an upper bound for the third-largest eigenvalue in a connected $r$-regular graph to have a $k$-factor in 2010. Gu found an upper bound

### 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)

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