Mathematics

Dr. Moumanti Podder
NYU-ECNU Institute of Mathematical Sciences, New York University

My work primarily concerns the Erd˝os-R´enyi random graphs G(n, p(n)) and random rooted trees, including the rooted Galton-Watson (GW) trees. I study properties of these random structures that are expressible either as first order sentences or as monadic second order sentences of mathematical logic. On GW trees with Poisson offspring, I give an almost complete characterization of the probabilities of first order sentences. On G(n, cn−1 ), I provide a complete set of completions for the almost sure theory of first order logic. On G(n, n−α), I study zero-one laws of existential first order sentences. Often, the probabilities of logical sentences on these random structures are obtained as solutions to finite systems of equations, and I investigate uniqueness and probabilistic interpretations of these solutions. I shall give a broad overview of the results as well as many questions that remain unanswered and serve as motivation for my future explorations. Time permitting, I shall touch upon my results and discussions on monadic second order logic, and my ongoing research on first order logic augmented with the ancestor relation on GW trees