## October 2022

### Konstantin Tikhomirov, A remark on the Ramsey number of the hypercube

Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]

A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper, we show that

### Nika Salia, Exact results for generalized extremal problems forbidding an even cycle

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

We determine the maximum number of copies of $K_{s,s}$ in a $C_{2s+2}$-free $n$-vertex graph for all integers $s \ge 2$ and sufficiently large $n$. Moreover, for $s\in\{2,3\}$ and any integer

### Xavier Goaoc, Order types and their symmetries

Room 1501, Bldg. E6-1, KAIST

Order types are a combinatorial classification of finite point sets used in discrete and computational geometry. This talk will give an introduction to these objects and their analogue for the

### Florent Koechlin, Uniform random expressions lack expressivity

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

In computer science, random expressions are commonly used to analyze algorithms, either to study their average complexity, or to generate benchmarks to test them experimentally. In general, these approaches only

### Dabeen Lee (이다빈), Non-smooth and Hölder-smooth submodular optimization

Room 1501, Bldg. E6-1, KAIST

We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an guarantee when the function is monotone

## November 2022

### Jungho Ahn (안정호), Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes

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

Let $\mathcal{F}$ be a family of graphs, and let $p$ and $r$ be nonnegative integers. The $(p,r,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$, there exists

### Hugo Jacob, On the parameterized complexity of computing tree-partitions

Zoom ID: 869 4632 6610 (ibsdimag)

Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender, Cornelissen, and van der Wegen, we consider the parameterized problem of computing a decomposition.

### Sebastian Wiederrecht, Excluding single-crossing matching minors in bipartite graphs

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

By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 Pólya asked for which (0, 1)-matrices A it is possible to change

### Chong Shangguan (上官冲), On the sparse hypergraph problem of Brown, Erdős and Sós

Zoom ID: 224 221 2686 (ibsecopro)

For fixed integers $r\ge 3, e\ge 3$, and $v\ge r+1$, let $f_r(n,v,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$

### Seonghyuk Im (임성혁), A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

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

A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices.  A linear $3$-graph is called a Steiner triple system if

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