2015/06/09 by Louigi Addario-Berry, Louigi Addario‐Berry, Addario-Berry, Louigi +12
Mathematics · #Chromatic scale #Clique #Combinatorics #Combinatorics (math.CO) #Dimension (graph theory) #Discrete mathematics #FOS: Mathematics #Graph #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Probability (math.PR) #Random graph #Statistics Theory (math.ST) #Stochastic processes and statistical mechanics #Upper and lower bounds #math.CO #math.PR #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1506.02811
arxiv created 2015/06/09 · openalex publication_date 2015/06/09 · arxiv updated 2015/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we explore maximal deviations of large random structures from their typical behavior. We introduce a model for a high-dimensional random graph process and ask analogous questions to those of Vapnik and Chervonenkis for deviations of averages: how "rich" does the process have to be so that one sees atypical behavior. In particular, we study a natural process of Erdős-Rényi random graphs indexed by unit vectors in ℝd. We investigate the deviations of the process with respect to three fundamental properties: clique number, chromatic number, and connectivity. In all cases we establish upper and lower bounds for the minimal dimension d that guarantees the existence of "exceptional directions" in which the random graph behaves atypically with respect to the property. For each of the three properties, four theorems are established, to describe upper and lower bounds for the threshold dimension in the subcritical and supercritical regimes.