Seminars in June 2017

  • (Distinguished Lecture) Terence Tao, The Erdős discrepancy problem

    (FYI: 2017 CMC Distinguished Lecture Series)

    The Erdős discrepancy problem
    Terence Tao
    Department of Mathematics, UCLA
    2017/06/15 4PM (Fusion Hall, KI Bldg.)
    The discrepancy of a sequence f(1), f(2), … of numbers is defined to be the largest value of |f(d) + f(2d) + … + f(nd)| as n,d range over the natural numbers. In the 1930s, Erdős posed the question of whether any sequence consisting only of +1 and -1 could have bounded discrepancy. In 2010, the collaborative Polymath5 project showed (among other things) that the problem could be effectively reduced to a problem involving completely multiplicative sequences. Finally, using recent breakthroughs in the asymptotics of completely multiplicative sequences by Matomaki and Radziwill, as well as a surprising application of the Shannon entropy inequalities, the Erdős discrepancy problem was solved in 2015. In this talk I will discuss this solution and its connection to the Chowla and Elliott conjectures in number theory.
    Tags:

  • Henry Liu, Highly connected subgraphs in sparse graphs
    Highly connected subgraphs in sparse graphs
    Henry Liu
    Central South University, Changsha, China
    2017/6/15 Thu 2PM-3PM
    Let G be a graph on n vertices with independence number α. How large must a k-connected subgraph G contain? We shall present the best possible answers when α=2 and α=3. Some open questions will also be presented.
    Joint work with Shinya Fujita (Yokohama City University, Japan) and Amites Sarkar (Western Washington University, USA).
    Tags:

  • O-joung Kwon (권오정), On low rank-width colorings
    On low rank-width colorings
    O-joung Kwon (권오정)
    Technische Universitat Berlin, Berin, Germany
    2017/6/09 Friday 11AM
    We introduce the concept of low rank-width colorings, generalizing the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [Grad and classes with bounded expansion I. Decompositions. EJC 2008]. We say that a class ? of graphs admits low rank-width colorings if there exist functions N:ℕ→ℕ and Q:ℕ→ℕ such that for all p∈ℕ, every graph G∈? can be vertex colored with at most N(p) colors such that the union of any i≤p color classes induces a subgraph of rank-width at most Q(i).
    Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class ? of bounded expansion and every positive integer r, the class {Gr: G∈?} of r-th powers of graphs from ?, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. In this talk, we provide the color refinement technique necessary to show the first result. This is joint work with Sebastian Sierbertz and Michał Pilipczuk.
    Tags:

Monthly Archives