### Debsoumya Chakraborti, Rainbow matchings in edge-colored simple graphs

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

There has been much research on finding a large rainbow matching in a properly edge-colored graph, where a proper edge coloring is a coloring of the edge set such that no same-colored edges are incident. Barát, Gyárfás, and Sárközy conjectured that in every proper edge coloring of a multigraph (with parallel edges allowed, but not

Livestream

### Joonkyung Lee (이준경), On common graphs

Zoom ID:8628398170 (123450)

A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdős, conjectured that every graph is common. The conjectures by Erdős and by Burr and Rosta were disproved by Thomason and

### Hong Liu (刘鸿), A solution to Erdős and Hajnal’s odd cycle problem

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

I will go over the history on the study of the set of cycle lengths of graphs with large average degree or chromatic number, and discuss recent work with Richard Montgomery on this topic. In particular, we will see the divergence of harmonic sum of odd cycle lengths in graphs with large chromatic number and

### Jinha Kim (김진하), On a conjecture by Kalai and Meshulam – the Betti number of the independence complex of ternary graphs

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

Given a graph G=(V,E), the independence complex of G is the abstract simplicial complex I(G) on V whose faces are the independent sets of G. A graph is ternary if it does not contain an induced cycle of length divisible by three. Kalai and Meshulam conjectured that if G is ternary then the sum of the Betti numbers

### O-joung Kwon (권오정), Directed tangles and applications

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

The canonical tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition

### Andreas Holmsen, Discrete geometry in convexity spaces

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

The notion of convexity spaces provides a purely combinatorial framework for certain problems in discrete geometry. In the last ten years, we have seen some progress on several open problems in the area, and in this talk, I will focus on the recent results relating to Tverberg’s theorem and the Alon-Kleitman (p,q) theorem.

### Ben Lund, Perfect matchings and derangements on graphs

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

We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G. This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph, and in terms of derangements and permutations on graphs. We give several related results and open questions. This

### Tuan Tran, Minimum saturated families of sets

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

A family $\mathcal F$ of subsets of is called s-saturated if it contains no s pairwise disjoint sets, and moreover, no set can be added to $\mathcal F$ while preserving this property. More than 40 years ago, Erdős and Kleitman conjectured that an s-saturated family of subsets of has size at least $(1 – 2^{-(s-1)})2^n$.

### Doowon Koh (고두원), On the cone restriction conjecture in four dimensions and applications in incidence geometry

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

Main purpose of this talk is to introduce a connection between restriction estimates for cones and point-sphere incidence theorems in the finite field setting. First, we review the finite field restriction problem for cones and address new results on the conical restriction problems. In particular, we establish the restriction conjecture for the cone in four

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

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