A limit law of almost l-partite graphs

DOI10.2178/JSL.7803110zbMATH Open1325.03033arXiv1204.2454OpenAlexW2018305354MaRDI QIDQ2869907FDOQ2869907

Vera Koponen

Publication date: 7 January 2014

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: For integers $lgeq2$, $dgeq1$ we study (undirected) graphs with vertices $1,\mathrm{...},n$ such that the vertices can be partitioned into $l$ parts such that every vertex has at most $d$ neighbours in its own part. The set of all such graphs is denoted $mb{P}_n(l,d)$. We prove a labelled first-order limit law, i.e., for every first-order sentence $varphi$, the proportion of graphs in $mb{P}_n(l,d)$ that satisfy $varphi$ converges as $noinfty$. By combining this result with a result of Hundack, Pr"omel and Steger cite{HPS} we also prove that if $1leq{s}_{1}leq\mathrm{...}leq{s}_l$ are integers, then $mbForb(mc{K}_{1,s_1,\mathrm{...},s_l})$ has a labelled first-order limit law, where $mbForb(mc{K}_{1,s_1,\mathrm{...},s_l})$ denotes the set of all graphs with vertices $1,\mathrm{...},n$, for some $n$, in which there is no subgraph isomorphic to the complete $(l+1)$-partite graph with parts of sizes $1,s_1,\mathrm{...},s_l$. In the course of doing this we also prove that there exists a first-order formula $xi$ (depending only on $l$ and $d$) such that the proportion of $mcGinmb{P}_n(l,d)$ with the following property approaches 1 as $noinfty$: there is a unique partition of $1,\mathrm{...},n$ into $l$ parts such that every vertex has at most $d$ neighbours in its own part, and this partition, viewed as an equivalence relation, is defined by $xi$.

Full work available at URL: https://arxiv.org/abs/1204.2454

Recommendations

• On limits of finite graphs
• From quasirandom graphs to graph limits and graphlets
• scientific article; zbMATH DE number 3285073
• A conjecture concerning a limit of non-Cayley graphs
• Hypergraph limits: A regularity approach
• On limit graphs of finite vertex-primitive graphs
• Asymptotic enumeration and limit laws of planar graphs
• Quasi-random graphs and graph limits
• Graph limits: An alternative approach to s‐graphons
• scientific article; zbMATH DE number 3946162

zbMATH Keywords

random graphfinite model theoryforbidden subgraphlimit lawextension properties

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13)

Cites Work

• The computational complexity of asymptotic problems. I: Partial orders
• The strange logic of random graphs
• Asymptotic probabilities of extension properties and random \(l\)-colourable structures
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• The typical structure of graphs without given excluded subgraphs
• The fine structure of octahedron-free graphs
• Extremal Graph Problems for Graphs with a Color-Critical Vertex
• The logic of random regular graphs
• A logical approach to asymptotic combinatorics I. First order properties
• Convergence law for random graphs with specified degree sequence

Cited In (2)

• DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law

This page was built for publication: A limit law of almost \(l\)-partite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869907)