Seminars in July 2017

  • Jaehoon Kim (김재훈), Property testing for hypergraphs
    Property testing for hypergraphs
    Jaehoon Kim (김재훈)
    School of Mathematics, Birmingham University, UK
    2017/7/27 Thu 4PM-5PM
    We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs).
    Here, a k-graph property ? is testable if there is a randomized algorithm which quickly distinguishes with high probability between k-graphs that satisfy ? and those that are far from satisfying ?. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. This is joint work with Felix Joos, Deryk Osthus and Daniela Kühn.
    Tags:

  • Johann A. Makowsky, The Complexity of Counting Generalized Colorings: New Results and Challenges
    The Complexity of Counting Generalized Colorings: New Results and Challenges
    Johann A. Makowsky
    Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
    2017/07/14 Fri 4PM-5PM
    Let P be a graph property. We look at graph colorings with k colors where each color class induces a graph satisfying P. By a result of Makowsky and Zilber (2005) the number of such colorings ?P(G;k) is a polynomial in k. We present recent results and open problems on the complexity of evaluating ?P(G;λ) for various properties P and (not only integer) values of λ.
    This is joint work with A. Goodall, M. Hermann, T. Kotek and S. Noble which was initiated during last year’s program “Counting Complexity and Phase Transitions”. See also arXiv:1701.06639v1.
    Tags:

  • June Huh (허준이), Negative correlation and Hodge-Riemann relations

    Discrete Math Seminar Joint with Algebraic Geometry Seminar

    Negative correlation and Hodge-Riemann relations
    June Huh (허준이)
    Institute for Advanced Study, Princeton, NJ, USA
    2017/07/12 Wednesday 4PM (Room 3435)
    All finite graphs satisfy the two properties mentioned in the title. I will explain what I mean by this, and speculate on generalizations and interconnections. This talk will be non-technical: Nothing will be assumed beyond basic linear algebra.
    Tags:

  • Changhyun Kwon (권창현), On the Price of Satisficing in Network User Equilibria
    On the Price of Satisficing in Network User Equilibria
    Changhyun Kwon (권창현)
    Industrial and Management Systems Engineering, University of South Florida
    2017/07/10 Mon 4PM-5PM
    When network users are satisficing decision-makers, the resulting traffic pattern attains a satisficing user equilibrium, which may deviate from the (perfectly rational) user equilibrium. In a satisficing user equilibrium traffic pattern, the total system travel time can be worse than in the case of the PRUE. We show how bad the worst-case satisficing user equilibrium traffic pattern can be, compared to the perfectly rational user equilibrium. We call the ratio between the total system travel times of the two traffic patterns the price of satisficing, for which we provide an analytical bound. Using the sensitivity analysis for variational inequalities, we propose a numerical method to quantify the price of satisficing for any given network instance.
    Tags:

  • Edgardo Roldán-Pensado, On the colourful Helly theorem
    On the colourful Helly theorem
    Edgardo Roldán-Pensado
    Instituto de Matemáticas, UNAM, Mexico
    2017/07/07 Fri 4PM-5PM
    Let F be a family of convex sets in R^d coloured using d+1 colours. Lovasz’s Colourful Helly Theorem states that if any colourful subfamily of convex sets is intersecting, then one of the monochromatic families is intersecting. We study what happens with the rest of the families.
    Tags:

  • Euiwoong Lee (이의웅), FPT Approximation Algorithms for Graph Problems
    FPT Approximation Algorithms for Graph Problems
    Euiwoong Lee (이의웅)
    Computer Science Department, Carnegie Mellon University
    2017/07/06 Thu 4PM-5PM
    Approximation algorithms and fixed-parameter tractable (FPT) algorithms have been two major ways to deal with NP-hardness of combinatorial optimization problems. The notion of FPT approximation can be naturally defined, and it is getting significant attention recently. Starting from gentle introductions to approximation algorithms and FPT algorithms, I will talk about my three recent results on FPT approximability.
    – Given a graph G = (V, E) and an integer k, we study k-Vertex Separator, where the goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most k vertices. We give an O(log k)-FPT approximation algorithm for k-Vertex Separator. Our result improves the best previous graph partitioning algorithms.
    – We also study k-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. We present an O(log k)-FPT approximation algorithm for k-Path Transversal. There was no nontrivial approximation algorithm for k > 4 before this work.
    – Finally, k-cut is the problem where we want to remove the minimum number of edges such that the graph has at least k connected components. We give a (2 – ε)-FPT approximation algorithm for some epsilon > 0, improving upon a (non-FPT) 2-approximation.
    The third result is joint work with Anupam Gupta and Jason Li.
    Tags:

Monthly Archives