It is proved that for every countable structure
In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs on
 NSFPAR ID:
 10051476
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Random Structures & Algorithms
 Volume:
 53
 Issue:
 2
 ISSN:
 10429832
 Page Range / eLocation ID:
 p. 185220
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump . We also show that this result does not hold for the limit ordinal . Moreover, we prove that there is no countable structure with the degree spectrum for . 
Abstract We study a new geometric bootstrap percolation model,
line percolation , on thed ‐dimensional integer grid. In line percolation with infection parameter r , infection spreads from a subsetof initially infected lattice points as follows: if there exists an axis‐parallel line L withr or more infected lattice points on it, then every lattice point ofon L gets infected, and we repeat this until the infection can no longer spread. The elements of the setA are usually chosen independently, with some densityp , and the main question is to determine, the density at which percolation (infection of the entire grid) becomes likely. In this paper, we determine up to a multiplicative factor of and up to a multiplicative constant as for every fixed . We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter. 
Abstract If
G is a graph andis a set of subgraphs of G , then an edge‐coloring ofG is called‐polychromatic if every graph from gets all colors present in G . The‐polychromatic number of G , denoted, is the largest number of colors such that G has an‐polychromatic coloring. In this article, is determined exactly when G is a complete graph andis the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph andis the family of all 2‐factors, or the family of all Hamiltonian cycles. 
Abstract A graph
G is said to be 2‐divisible if for all (nonempty) induced subgraphsH ofG ,can be partitioned into two sets such that and . (Here denotes the clique number of G , the number of vertices in a largest clique ofG ). A graphG is said to be perfectly divisible if for all induced subgraphsH ofG ,can be partitioned into two sets such that is perfect and . We prove that if a graph is ‐free, then it is 2‐divisible. We also prove that if a graph is bull‐free and either odd‐hole‐free or P _{5}‐free, then it is perfectly divisible. 
Abstract Given a graph
, its auxiliary square‐graph is the graph whose vertices are the non‐edges of and whose edges are the pairs of non‐edges which induce a square (i.e., a 4‐cycle) in . We determine the threshold edge‐probability at which the Erdős–Rényi random graph begins to asymptotically almost surely (a.a.s.) have a square‐graph with a connected component whose squares together cover all the vertices of . We show , a polylogarithmic improvement on earlier bounds on due to Hagen and the authors. As a corollary, we determine the threshold at which the random right‐angled Coxeter group a.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence.