### Jaiung Jun (전재웅), On the Hopf algebra of multi-complexes

Zoom ID: 934 3222 0374 (ibsdimag)

In combinatorics, Hopf algebras appear naturally when studying various classes of combinatorial objects, such as graphs, matroids, posets or symmetric functions. Given such a class of combinatorial objects, basic information on these objects regarding assembly and disassembly operations are encoded in the algebraic structure of a Hopf algebra. One then hopes to use algebraic identities of

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

### Paul Seymour, The Erdős-Hajnal conjecture is true for excluding a five-cycle

Zoom ID: 934 3222 0374 (ibsdimag)

In an n-vertex graph, there must be a clique or stable set of size at least $C\log n$, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph, the largest clique or stable set is bigger. Erdős and Hajnal conjectured in 1977 that

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

### Rose McCarty, Vertex-minors and flooding immersions

Zoom ID: 934 3222 0374 (ibsdimag)

An immersion of a graph H into a graph G sends edges of H into edge-disjoint trails of G. We say the immersion is flooding if every edge of G is in one of the trails. Flooding immersions are interesting for Eulerian group-labelled graphs; in this context they behave quite differently from regular immersions. Moreover,

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

### Yusuke Kobayashi (小林 佑輔), An FPT Algorithm for Minimum Additive Spanner Problem

Zoom ID: 934 3222 0374 (ibsdimag)

For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph,

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

### Dong Yeap Kang (강동엽), A proof of the Erdős-Faber-Lovász conjecture

Zoom ID: 934 3222 0374 (ibsdimag)

A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this talk, I will present the ideas to prove the conjecture for

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