Casey Tompkins, Saturation problems in the Ramsey theory of graphs, posets and point sets

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

In 1964, Erdős, Hajnal and Moon introduced a saturation version of Turán's classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other

Sang-il Oum (엄상일), Survey on vertex-minors

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

For a vertex v of a graph G, the local complementation at v is an operation to obtain a new graph denoted by G*v from G such that two distinct vertices x, y are adjacent in G*v if and only if both x, y are neighbors of v and x, y are non-adjacent, or at least one

Seunghun Lee (이승훈), Leray numbers of complexes of graphs with bounded matching number

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

Given a graph $G$ on the vertex set $V$, the non-matching complex of $G$, $\mathsf{NM}_k(G)$, is the family of subgraphs $G' \subset G$ whose matching number $\nu(G')$ is strictly less than $k$. As an attempt to generalize the result by Linusson, Shareshian and Welker on the homotopy types of $\mathsf{NM}_k(K_n)$ and $\mathsf{NM}_k(K_{r,s})$ to arbitrary graphs

Canceled

KSIAM 2020 Spring Conference (cancelled)

IBS Science Culture Center

KSIAM 2020 Spring Conference will be held at IBS from May 8, 2020 to May 9, 2020. Organized by Korean Society for Industrial and Applied Mathematics. Organizing Committee Myungjoo Kang (Seoul National University) (chair) Ahn, Jaemyung (KAIST) Kwon, Hee-Dae (Inha University) Lee, Eun Jung (Yonsei University) Jang, Bongsoo (UNIST) Jung, Miyoun (Hankuk University of Foreign

Eun Jung Kim (김은정), Twin-width: tractable FO model checking

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

Inspired by a width invariant defined on permutations by Guillemot and Marx , we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes

O-joung Kwon (권오정), Mim-width: a width parameter beyond rank-width

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

Vatshelle (2012) introduced a width parameter called mim-width. It is based on the following cut function : for a vertex partition (A,B) of a graph, the complexity of this partition is computed by the size of a maximum induced matching of the bipartite subgraph induced by edges between A and B. This parameter naturally extends

Hong Liu (刘鸿), Asymptotic Structure for the Clique Density Theorem

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

The famous Erdős-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all r was determined only recently, by Reiher . Here we describe the asymptotic structure of all almost extremal graphs.

Huy-Tung Nguyen, The average cut-rank of graphs

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

The cut-rank of a set X of vertices in a graph G is defined as the rank of the X×(V(G)∖X) matrix over the binary field whose (i,j)-entry is 1 if the vertex i in X is adjacent to the vertex j in V(G)∖X and 0 otherwise. We introduce the graph parameter called the average cut-rank

Jiseung Kim (김지승), Hardness and concrete security in cryptography

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

Computationally hard problems have been widely used to construct cryptographic primitives such as encryptions, digital signatures. For example, provably secure primitives are based on a reduction from the hardness problems. However, the concrete instantiation of primitives does not follow the results of hardness problems due to its efficiency. In this talk, we introduce cryptographic hardness

Andreas Holmsen, Fractional Helly and topological complexity

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

The fractional Helly theorem is a simple yet remarkable generalization of Helly's classical theorem on the intersection of convex sets, and it is of considerable interest to extend the fractional Helly theorem beyond the setting of convexity. In this talk I will discuss a recent result which shows that the fractional Helly theorem holds for families

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.