Главная

M. E. Malliaris

  1. Edge distribution and density in the characteristic sequence.

    Втр, 09/15/2009 - 11:27 — SomNambul
    Authors: M. E. Malliaris
    Subjects: Logic
    Abstract

    The characteristic sequence of hypergraphs $<P_n : n<\omega>$ associated to a
    formula $\phi(x;y)$, introduced in [arXiv:0908.4111], is defined by
    $P_n(y_1,... y_n) = (\exists x) \bigwedge_{i\leq n} \phi(x;y_i)$. This paper
    continues the study of characteristic sequences, showing that graph-theoretic
    techniques, notably Szemer\'edi's celebrated regularity lemma, can be naturally
    applied to the study of model-theoretic complexity via the characteristic
    sequence.

  2. Persistence and NIP in the characteristic sequence.

    Пнд, 08/31/2009 - 17:16 — SomNambul
    Authors: M. E. Malliaris
    Subjects: Logic
    Abstract

    For a first-order formula $\phi(x;y)$ we introduce and study the
    characteristic sequence $<P_n : n < \omega>$ of hypergraphs defined by
    $P_n(y_1,...,y_n) := (\exists x) \bigwedge_{i \leq n} \phi(x;y_i)$. We show
    that combinatorial and classification theoretic properties of the
    characteristic sequence reflect classification theoretic properties of
    $\varphi$ and vice versa.

Math-arch

RSS-материал