Seminars in November 2018

  • Ilkyoo Choi (최일규), Largest 2-regular subgraphs in 3-regular graphs
    Largest 2-regular subgraphs in 3-regular graphs
    Ilkyoo Choi (최일규)
    Department of Mathematics, Hankuk University of Foreign Studies, Yongin-si
    2018/11/26 Mon 5PM-6PM (Bldg. E6-1, Room 1401)
    For a graph G, let f2(G) denote the largest number of vertices in a 2-regular subgraph of G. We determine the minimum of f2(G) over 3-regular n-vertex simple graphs G.
    To do this, we prove that every 3-regular multigraph with exactly c cut-edges has a 2-regular subgraph that omits at most max{0,⎣(c-1)/2⎦} vertices.
    More generally, every n-vertex multigraph with maximum degree 3 and m edges has a 2-regular subgraph that omits at most max{0, ⎣(3n-2m+c-1)/2⎦} vertices.
    These bounds are sharp; we describe the extremal multigraphs.
    This is joint work with Ringi Kim, Alexandr V. Kostochka, Boram Park, and Douglas B. West.
    Tags:

  • Euiwoong Lee (이의웅), Faster Exact and Approximate Algorithms for k-Cut
    Faster Exact and Approximate Algorithms for k-Cut
    Euiwoong Lee (이의웅)
    Courant Institute of Mathematical Sciences, NYU, New York, USA
    2018/11/13 Tue 5PM (Bldg. E6-1, Room 1401)
    In the k-cut problem, we are given an edge-weighted graph G and an integer k, and have to remove a set of edges with minimum total weight so that G has at least k connected components. This problem has been studied various algorithmic perspectives including randomized algorithms, fixed-parameter tractable algorithms, and approximation algorithms. Their proofs of performance guarantees often reveal elegant structures for cuts in graphs.
    It has still remained an open problem to (a) improve the runtime of exact algorithms, and (b) to get better approximation algorithms. In this talk, I will give an overview on recent progresses on both exact and approximation algorithms. Our algorithms are inspired by structural similarities between k-cut and the k-clique problem.
    Tags:

  • Euiwoong Lee (이의웅), Bridging Continuous and Discrete Optimization through the Lens of Approximation

    [FYI: Colloquium, School of Computing]

    Bridging Continuous and Discrete Optimization through the Lens of Approximation
    Euiwoong Lee (이의웅)
    Courant Institute of Mathematical Sciences, NYU, New York, USA
    2018/11/12 Mon 4PM (Bldg. E3-1, Room 1501)
    Mathematical optimization is a field that studies algorithms, given an objective function and a feasible set, to find the element that maximizes or minimizes the objective function from the feasible set. While most interesting optimization problems are NP-hard and unlikely to admit efficient algorithms that find the exact optimal solution, many of them admit efficient “approximation algorithms” that find an approximate optimal solution.
    Continuous and discrete optimization are the two main branches of mathematical optimization that have been primarily studied in different contexts. In this talk, I will introduce my recent results that bridge some of important continuous and discrete optimization problems, such as matrix low-rank approximation and Unique Games. At the heart of the connection is the problem of approximately computing the operator norm of a matrix with respect to various norms, which will allow us to borrow mathematical tools from functional analysis.
    Tags:

  • Dong Yeap Kang (강동엽), On the rational Turán exponents conjecture
    On the rational Turán exponents conjecture
    Dong Yeap Kang (강동엽)
    Department of Mathematical Sciences, KAIST
    2018/11/5 Mon 5PM-6PM
    The extremal number ex(n,F) of a graph F is the maximum number of edges in an n-vertex graph not containing F as a subgraph. A real number r∈[1,2] is realisable if there exists a graph F with ex(n , F) = Θ(nr). Several decades ago, Erdős and Simonovits conjectured that every rational number in [1,2] is realisable. Despite decades of effort, the only known realisable numbers are 1,7/5,2, and the numbers of the form 1+(1/m), 2-(1/m), 2-(2/m) for integers m≥1. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2.
    We discuss some recent progress on the conjecture of Erdős and Simonovits. First, we show that 2-(a/b) is realisable for any integers a,b≥1 with b>a and b≡±1 (mod a). This includes all previously known ones, and gives infinitely many limit points 2-(1/m) in the set of all realisable numbers as a consequence.
    Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.
    This is joint work with Jaehoon Kim and Hong Liu.
    Tags:

Monthly Archives