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, …
10 events found.
Discrete Math Seminar
-
-
-
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 …
-
-
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 …
-
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 …
-
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 …
-
-
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 …
-
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. …
-
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 …
-
Jaehoon Kim (김재훈), A resilience version of Pósa’s theorem
Room B232 IBS (기초과학연구원)Pósa's theorem states that any graph G whose degree sequence $d_1\leq \dots \leq d_n$ satisfies $d_i \geq i+1$ for all $i< n/2$ has a Hamilton cycle. This degree condition is …
-
Dennis Wong, Generating Gray codes and universal cycles for weak orders
Room B232 IBS (기초과학연구원)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 …