## June 2022

### Amadeus Reinald, Twin-width and forbidden subdivisions

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

Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, problems expressible in FO logic can be solved in FPT time when provided

### Ben Lund, Radial projections in finite space

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

Given a set $E$ and a point $y$ in a vector space over a finite field, the radial projection $\pi_y(E)$ of $E$ from $y$ is the set of lines that

## July 2022

### Eric Vigoda, Computational phase transition and MCMC algorithms

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

This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to

### Kevin Hendrey, Product Structure of Graph Classes with Bounded Treewidth

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

The strong product $G\boxtimes H$ of graphs $G$ and $H$ is the graph on the cartesian product $V(G)\times V(H)$ such that vertices $(v,w)$ and $(x,y)$ are adjacent if and only

### Jinyoung Park (박진영), Thresholds 1/2

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

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on

### Jinyoung Park (박진영), Thresholds 2/2

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

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on

## August 2022

### Seunghun Lee (이승훈), Inscribable order types

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

We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk, we investigate inscribability of

### Eun Jung Kim (김은정), Directed flow-augmentation

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

We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers $s,t\in V(G)$, and an integer $k$, adds (randomly) to

### Noleen Köhler, Testing first-order definable properties on bounded degree graphs

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

Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability

### Raul Lopes, Temporal Menger and related problems

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

A temporal graph is a graph whose edges are available only at specific times. In this scenario, the only valid walks are the ones traversing adjacent edges respecting their availability,

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