Accueil

Péter L. Erdős

  1. Caterpillar dualities and regular languages.

    Thu, 03/08/2012 - 15:01 — SomNambul
    Authors: Péter L. Erdős, Claude Tardif, Gábor Tardos
    Subjects: Combinatorics
    Abstract

    We characterize obstruction sets in caterpillar dualities in terms of regular
    languages, and give a construction of the dual of a regular family of
    caterpillars. We show that these duals correspond to the constraint
    satisfaction problems definable by a monadic linear Datalog program with at
    most one EDB per rule.

  2. Balanced Vertices in Trees and a Simpler Algorithm to Compute the Genomic Distance.

    Mon, 04/19/2010 - 15:02 — SomNambul
    Authors: Péter L. Erdős, Lajos Soukup, Jens Stoye
    Subjects: Discrete Mathematics
    Abstract

    This paper provides a short and transparent solution for the covering cost of
    white-grey trees which play a crucial role in the algorithm of Bergeron {\it et
    al.}\ to compute the rearrangement distance between two multichromosomal
    genomes in linear time ({\it Theor. Comput. Sci.}, 410:5300-5316, 2009). In the
    process it introduces a new {\em center} notion for trees, which seems to be
    interesting on its own.

  3. Towards random uniform sampling of bipartite graphs with given degree sequence.

    Fri, 04/16/2010 - 15:01 — SomNambul
    Authors: Péter L. Erdős, Lajos Soukup, Istán Miklós
    Subjects: Combinatorics
    Abstract

    In this paper we consider a simple Markov chain for bipartite graphs with
    given degree sequence on $n$ vertices. We show that the mixing time of this
    Markov chain is bounded above by a polynomial in $n$ in case of {\em
    semi-regular} degree sequence. The novelty of our approach lays in the
    construction of the canonical paths in Sinclair's method.

  4. Degree-based graph construction.

    Wed, 08/26/2009 - 14:58 — SomNambul
    Authors: Hyunju Kim, Zoltan Toroczkai, Péter L. Erdős, István Miklós, László Á. Székely
    Subjects: Combinatorics
    Abstract

    Degree-based graph construction is an ubiquitous problem in network modeling,
    ranging from social sciences to chemical compounds and biochemical reaction
    networks in the cell. This problem includes existence, enumeration, exhaustive
    construction and sampling questions with aspects that are still open today.
    Here we give necessary and sufficient conditions for a sequence of nonnegative
    integers to be realized as a simple graph's degree sequence, such that a given
    (but otherwise arbitrary) set of connections from a arbitrarily given node are
    avoided.

Math-arch

Syndicate content