Department Seminars & Colloquia
When you're logged in, you can subscribe seminars via e-mail
Room B232, IBS (기초과학연구원)
Discrete Math
Seog-Jin Kim (Konkuk University)
Signed colouring and list colouring of k-chromatic graphs
Room B232, IBS (기초과학연구원)
Discrete Math
A signed graph is a pair (G, σ), where G is a graph and σ: E(G) → {1,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G,σ) is a mapping f:V(G) → Nk such that for each edge e=uv, f(x)≠σ(e) f(y), where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G, (G, σ) has a k-colouring.
Let f(n,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G, for any signature σ on G, there is a proper L-colouring of (G, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.
A Verra fourfold is a smooth projective complex variety defined as a double cover of P^2x P^2 branched along a divisor of bidegree (2,2).
These varieties are similar to cubic fourfolds in several ways (Hodge theory, relation to hyperkaehler fourfolds, derived categories).
Inspired by these multiple analogies, I consider the Chow ring of a Verra fourfold. Among other things, I will show that the multiplicative structure of this Chow ring has a curious K3-like property.
The generalized Franchetta conjecture as formulated by O’Grady is about algebraic cycles on the universal K3 surface. It is natural to consider a similar conjecture for algebraic cycles on universal families of hyperkaehler varieties. This has close ties to Beauville’s conjectural ``splitting property’’, and the Beauville-Voisin conjecture (stating that the Chow ring of a hyperkaehler variety has a certain subring injecting into cohomology). In my talk, I will attempt to give an overview of these conjectures, and present some cases where they can be proven. This is joint work with Lie Fu, Charles Vial and Mingmin Shen.
A flag Bott tower is a sequence of flag bundles such that each stage of which comes from the induced full-flag bundle of a sum of holomorphic line bundles. A flag Bott manifold is not toric variety but it has a torus action. In this talk, we consider the standard torus action on a flag Bott manifold and compute its equivariant cohomology ring.
Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design.
In this talk, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds, namely μ(I)=2LP(I)-IP(dual-I). Here, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result, we obtain an algorithm running in time 4^(k-μ(I)) for multiway cut and its generalizations, where k is the budget for a solution.
This talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.
A celebrated conjecture of Sidorenko and Erdős–Simonovits states that, for all bipartite graphs H, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion.
Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary, we have that for every bipartite graph H with bipartition A∪B, there is a positive integer p such that the blow-up H_A^p formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Joint work with David Conlon.
The prime geodesic theorem allows one to count the number of closed geodesics having length less than X in a given hyperbolic manifold. As a naive generalization of the prime geodesic theorem, we are interested in the the number of immersed totally geodesic surfaces in a given hyperbolic manifold. I am going to talk about this question when the underlying hyperbolic manifold is an arithmetic hyperbolic $3$-manifold corresponding to a Bianchi group SL(2,O_{-d}), where O_{-d} is the ring of integers of Q[sqrt{-d}] for some positive integer d.
This series of lecture will introduce the study of groups acting on the circle and the line, the moduli spaces of such actions, and the role of these spaces in questions of geometric topology, dynamics, and foliation theory. I will focus on new rigidity results in low regularity, surveying important techniques, geometrically motivated examples, and open problems.
We propose a novel class of Hawkes-based model that assesses two types of systemic risk in high-frequency price processes: the endogenous systemic risk within a single process and the interactive systemic risk between a couple of processes. We examine the existence of systemic risk at a microscopic level via an empirical analysis of the futures markets of the West Texas Intermediate (WTI) crude oil and gasoline and perform a comparative analysis with the conditional value-at-risk as a benchmark measure of the proposed model. Throughout the analysis, we uncover remarkable empirical findings in terms of the high-frequency structure of the two markets: for the past decade, the level of endogenous systemic risk in the WTI market was significantly higher than that in the gasoline market. Moreover, the level at which the gasoline price affects the WTI price was constantly higher than in the opposite case. Although the two prices interact with each other at the transaction-unit level, the degree of relative influences on the two markets, that is, from the WTI to the gasoline and vice versa, was very asymmetric, but that difference has reduced gradually over time.
This series of lecture will introduce the study of groups acting on the circle and the line, the moduli spaces of such actions, and the role of these spaces in questions of geometric topology, dynamics, and foliation theory. I will focus on new rigidity results in low regularity, surveying important techniques, geometrically motivated examples, and open problems.
Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log ???)-approximation algorithm for packing subgraphs containing an H-minor.
This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.
This series of lecture will introduce the study of groups acting on the circle and the line, the moduli spaces of such actions, and the role of these spaces in questions of geometric topology, dynamics, and foliation theory. I will focus on new rigidity results in low regularity, surveying important techniques, geometrically motivated examples, and open problems.
Let X be a compact Kahler manifold of dimension n > 0. Let G be a group of zero entropy automorphisms of X.
Let G_0 be the set of elements in G which are isotopic to the identity. We prove that after replacing G by a suitable finite-index subgroup,
G/G_0 is a unipotent group of derived length at most n-1. This is a corollary of an optimal upper bound of length involving the Kodaira dimension.
We also study the algebro-geometric structure of X when it admits a group action with maximal derived length n-1.
This is a joint work with Dinh and Oguiso.
Given a group G and a manifold M, can one describe all the actions of G on M? This is a basic, natural question in geometric topology, but also a very difficult one -- even in the case where M is 1-dimensional, and G is a familiar, finitely generated group.
This talk will introduce the theory of groups acting on 1-manifolds, through the study of orderable groups. I will describe some connections between this theory and themes in topology and dynamics (like rigidity and foliation theory ), some current open problems, and indicate new approaches coming from recent joint work with C. Rivas.