Accueil

Asaf Shapira

  1. A Note on the Balanced ST-Connectivity.

    Thu, 04/05/2012 - 15:01 — SomNambul
    Authors: Asaf Shapira, Shiva Kintali
    Subjects: Computational Complexity
    Abstract

    We prove that every YES instance of Balanced ST-Connectivity has a balanced
    path of polynomial length.

  2. Finding Cycles and Trees in Sublinear Time.

    Tue, 07/27/2010 - 15:02 — SomNambul
    Authors: Asaf Shapira, Artur Czumaj, Oded Goldreich, Dana Ron, Christian Sohler
    Subjects: Data Structures and Algorithms
    Abstract

    We present sublinear-time (randomized) algorithms for finding simple cycles
    of length at least $k\geq 3$ and tree-minors in bounded-degree graphs. The
    complexity of these algorithms is related to the distance of the graph from
    being $C_k$-minor-free (resp., free from having the corresponding tree-minor).
    In particular, if the graph is far (i.e., $\Omega(1)$-far) {from} being
    cycle-free, i.e.

  3. The Quasi-Randomness of Hypergraph Cut Properties.

    Tue, 02/02/2010 - 16:01 — SomNambul
    Authors: Asaf Shapira, Raphael Yuster
    Subjects: Combinatorics
    Abstract

    Let a_1,...,a_k satisfy a_1+...+a_k=1 and suppose a k-uniform hypergraph on n
    vertices satisfies the following property; in any partition of its vertices
    into k sets A_1,...,A_k of sizes a_1*n,...,a_k*n, the number of edges
    intersecting A_1,...,A_k is the number one would expect to find in a random
    k-uniform hypergraph. Can we then infer that H is quasi-random? We show that
    the answer is negative if and only if a_1=...=a_k=1/k. This resolves an open
    problem raised in 1991 by Chung and Graham [J. AMS '91].

  4. Color-Critical Graphs Have Logarithmic Circumference.

    Mon, 08/24/2009 - 13:10 — SomNambul
    Authors: Asaf Shapira, Robin Thomas
    Subjects: Combinatorics
    Abstract

    A graph G is k-critical if every proper subgraph of G is (k-1)-colorable, but
    the graph G itself is not. We prove that every k-critical graph on n vertices
    has a cycle of length at least log n/(100log k), improving a bound of Alon,
    Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that the
    bound cannot be improved to exceed 2(k-1)log n/log(k-2). We thus settle the
    problem of bounding the minimal circumference of k-critical graphs, raised by
    Dirac in 1952 and Kelly and Kelly in 1954.

Math-arch

Syndicate content