### Martin Ziegler, Quantitative Coding and Complexity Theory of Continuous Data

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

Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices, characters as integers, integers as bit strings, and vice versa. For such discrete data, the actual encoding is usually straightforward and/or complexity-theoretically inessential (up to polynomial time, say). But concerning continuous data, already real numbers naturally suggest various encodings with very different computational properties.

### Minki Kim (김민기), Rainbow paths and rainbow matchings

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

We prove that if $n \geq 3$, then any family of $3n-3$ sets of matchings of size $n$ in any graph has a rainbow matching of size $n$. This improves on a previous result, in which $3n-3$ is replaced by $3n-2$. We also prove a "cooperative" generalization: for $t > 0$ and $n \geq 3$,

### Kevin Hendrey, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

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

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles.  However, in 1999, Reed proved an analogue for odd cycles by relaxing packing

### Debsoumya Chakraborti, Some classical problems in graph saturation

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

Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph $G$ is called $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$, but the addition of any edge creates a copy of $F$. The function $\operatorname{sat}(n,F)$ is defined to be the minimum number of edges in an $n$-vertex

### Se-Young Yun (윤세영), Regret in Online Recommendation Systems

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

We propose a theoretical analysis of recommendation systems in an online setting, where items are sequentially recommended to users over time. In each round, a user, randomly picked from a population of m users, requests a recommendation. The decision-maker observes the user and selects an item from a catalogue of n items. Importantly, an item

### Hong Liu (刘鸿), Nested cycles with no geometric crossing

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

In 1975, Erdős asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each

### Casey Tompkins, 3-uniform hypergraphs avoiding a cycle of length four

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

We show that that the maximum number of of edges in a $3$-uniform hypergraph without a Berge-cycle of length four is at most $(1+o(1)) \frac{n^{3/2}}{\sqrt{10}}$. This improves earlier estimates by Győri and Lemons and by Füredi and Özkahya. Joint work with Ergemlidze, Győri, Methuku, Salia.

### Rutger Campbell, Matroid orientability and representability

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

In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.

### William Overman, Some Ordered Ramsey Numbers of Graphs on Four Vertices

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

Ordered Ramsey numbers were introduced in 2014 by Conlon, Fox, Lee, and Sudakov. Their results included upper bounds for general graphs and lower bounds showing separation from classical Ramsey numbers. We show the first nontrivial results for ordered Ramsey numbers of specific small graphs. In particular we prove upper bounds for orderings of graphs on four vertices,

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

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

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.

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