Jeong Ok Choi (최정옥), Various game-theoretic models on graphs

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

We introduce some of well-known game-theoretic graph models and related problems. A contagion game model explains how an innovation diffuses over a given network structure and focuses on finding conditions on which structure an innovation becomes epidemic. Regular infinite graphs are interesting examples to explore. We show that regular infinite trees make an innovation least

Jaeseong Oh (오재성), A 2-isomorphism theorem for delta-matroids

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

Whitney’s 2-Isomorphism Theorem characterises when two graphs have isomorphic cycle matroids. In this talk, we present an analogue of this theorem for graphs embedded in surfaces by characterising when two graphs in surface have isomorphic delta-matroids. This is based on the joint work with Iain Moffatt.

Daniel Cranston, Vertex Partitions into an Independent Set and a Forest with Each Component Small

Zoom ID: 869 4632 6610 (ibsdimag)

For each integer $k\ge 2$, we determine a sharp bound on $\operatorname{mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$, where $I$ is an independent set and $G$ is a forest in which each component has at most k vertices. For each $k$ we construct an infinite family of examples showing our result is best

Casey Tompkins, Extremal forbidden poset problems in Boolean and linear lattices

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

Extending the classical theorem of Sperner on the maximum size of an antichain in the Boolean lattice, Katona and Tarján introduced a general extremal function $La(n,P)$, defined to be the maximum size of a family of subsets of $$ which does not contain a given poset $P$ among its containment relations.  In this talk, I

Meike Hatzel, Constant congestion bramble

Zoom ID: 869 4632 6610 (ibsdimag)

In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Paweł Komosa and Manuel Sorge. A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap

Yijia Chen (陈翌佳), Graphs of bounded shrub-depth, through a logic lens

Zoom ID: 869 4632 6610 (ibsdimag)

Shrub-depth is a graph invariant often considered as an extension of tree-depth to dense graphs. In this talk I will explain our recent proofs of two results about graphs of bounded shrub-depth. Every graph property definable in monadic-second order logic, e.g., 3-colorability, can be evaluated by Boolean circuits of constant depth and polynomial size, whose

Duksang Lee (이덕상), Characterizing matroids whose bases form graphic delta-matroids

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

We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for

Da Qi Chen, Bipartite Saturation

Zoom ID: 869 4632 6610 (ibsdimag)

In extremal graph theory, a graph G is H-saturated if G does not contain a copy of H but adding any missing edge to G creates a copy of H. The saturation number, sat(n, H), is the minimum number of edges in an n-vertex H-saturated graph. This class of problems was first studied by Zykov

Livestream

Joonkyung Lee (이준경), On Ramsey multiplicity

Zoom ID:8628398170 (123450)

Ramsey's theorem states that, for a fixed graph $H$, every 2-edge-colouring of $K_n$ contains a monochromatic copy of $H$ whenever $n$ is large enough. Perhaps one of the most natural questions after Ramsey's theorem is then how many copies of monochromatic $H$ can be guaranteed to exist. To formalise this question, let the Ramsey multiplicity

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

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.