Rose McCarty, Vertex-minors and flooding immersions

Zoom ID: 869 4632 6610 (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

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: 869 4632 6610 (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

Ron Aharoni, Colorful KKM and multiple cakes division

Zoom ID: 869 4632 6610 (ibsdimag)

In the "cake partition" problem n players have each a list of preferred parts for any partition of the interval ("cake") into n sub-intervals. Woodall, Stromquist and Gale proved independently that under mild conditions on the list of preferences (like continuity) there is always a partition and assignment of parts to the players, in which every player gets

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

Jie Ma (马杰), Non-repeated cycle lengths and Sidon sequences

Zoom ID: 869 4632 6610 (ibsdimag)

We prove a conjecture of Boros, Caro, Furedi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths, which is a restricted version of a longstanding problem of Erdos. Our proof together with the matched lower bound construction of Boros, Caro, Furedi and Yuster show that this problem can

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.

David Wood, Tree densities of sparse graph classes

Zoom ID: 869 4632 6610 (ibsdimag)

This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $\mathcal{G}$ as $n\to \infty$? I will answer this question for a variety of sparse graph classes $\mathcal{G}$. In particular, we show that the answer is

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