Jungho Ahn (안정호), A coarse Erdős-Pósa theorem for constrained cycles

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

An induced packing of cycles in a graph is a set of vertex-disjoint cycles such that the graph has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem shows that for every positive integer k, every graph contains k vertex-disjoint cycles or a set of O(klogk) vertices which intersects every cycle of G.

O-joung Kwon (권오정), Erdős-Pósa property of A-paths in unoriented group-labelled graphs

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

A family F of graphs is said to satisfy the Erdős-Pósa property if there exists a function f such that for every positive integer k, every graph G contains either k (vertex-)disjoint subgraphs in F or a set of at most f(k) vertices intersecting every subgraph of G in F. We characterize the obstructions to

Sepehr Hajebi, The pathwidth theorem for induced subgraphs

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

We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The

Irene Muzi, An elementary bound for Younger’s conjecture

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

In 1996, Reed, Robertson, Seymour and Thomas proved Younger's Conjecture, which states that for all directed graphs D, there exists a function f such that if D does not contain k disjoint cycles, D contains a feedback vertex set, i.e. a subset of vertices whose deletion renders the graph acyclic, of size bounded by f(k).

Johannes Carmesin, Open problems in graph theory

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

Since the proof of the graph minor structure theorem by Robertson and Seymour in 2004, its underlying ideas have found applications in a much broader range of settings than their original context. They have driven profound progress in areas such as vertex minors, pivot minors, matroids, directed graphs, and 2-dimensional simplicial complexes. In this talk,

Michał Seweryn, Dimension and standard examples in planar posets

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

The dimension of a poset is the least integer d such that the poset is isomorphic to a subposet of the product of d linear orders. In 1983, Kelly constructed planar posets of arbitrarily large dimension. Crucially, the posets in his construction involve large standard examples, the canonical structure preventing a poset from having small

Hyunwoo Lee (이현우), Reconstructing hypergraph matching polynomials

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

By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all nk2, one can reconstruct the matching polynomial of an n-vertex k-uniform hypergraph from the multiset of all induced sub-hypergraphs on k1kn+1 vertices. This generalizes the well-known result of

Marcelo Garlet Milani, Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem

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

In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem. The theorem states the existence of a function f such that every digraph of directed tree-width f(k) contains a cylindrical grid of order k as a butterfly minor, but the given function grows non-elementarily with the size of the grid minor. We present an alternative

Daniel McGinnis, A necessary and sufficient condition for k-transversals

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

We solve a long-standing open problem posed by Goodman and Pollack in 1988 by establishing a necessary and sufficient condition for a finite family of convex sets in Rd to admit a k-transversal (a k-dimensional affine subspace that intersects each set) for any 0kd1. This result is a common generalization of

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.