Seunghun Lee (이승훈), Leray numbers of complexes of graphs with bounded matching number
Room B232 IBS (기초과학연구원)Given a graph
Given a graph
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 …
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,
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 …
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. …
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 …
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 …
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 …
Pósa's theorem states that any graph G whose degree sequence
A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics, designing combination locks, and even in horse racing. In this talk, we present new and simple algorithms to generate Gray codes and universal cycles for weak orders.