Vera Koponen
email: vera.koponen@math.uu.se

Random graphs with bounded maximum degree: asymptotic structure and a logical limit law

Keywords: random graph, bounded degree, finite model theory, limit law

For any fixed integer R ≥ 2 we characterise the typical structure of undirected graphs with vertices 1, . . . , n and maximum degree R, as n tends to infinity. The information is used to prove that such graphs satisfy a labelled limit law for first-order logic. If R ≥ 5 then also an unlabelled limit law holds.

Introduction

This article is concerned with finite graphs with n vertices labelled 1, . . . , n such that every vertex has degree at most R, where R will be a fixed non-negative integer. By graph we always mean finite undirected graph. The asymptotic structure of such graphs have been studied before, in numerous articles, in the case when a degree sequence is associated and one considers (only) graphs with this degree sequence. Two variants of degree sequences have been considered. In one variant a sequence d = (d 1 , . . . , d n ) of non-negative integers is given and one studies the graphs with vertices 1, . . . , n such that, for every i = 1, . . . , n, the vertex i has degree d i . In the other variant we are given a sequence d = (d 0 , d 1 , . . . , d R ) and study the graphs with vertices 1, . . . , n such that exactly d i vertices have degree i. Early work on graphs with prescribed degree sequence include [START_REF] Bender | The asymptotic number of labelled graphs with given degree sequences[END_REF][START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF][START_REF] Wormald | The asymptotic connectivity of labelled regular graphs[END_REF][START_REF] Wormald | The asymptotic distribution of short cycles in random regular graphs[END_REF][START_REF] Mckay | Automorphisms of random graphs with specified vertices[END_REF]. In particular one can consider degree sequences (d 1 , . . . , d n ) in which all entries are the same, say r, in which case one gets r-regular graphs. This special case has also been studied extensively, for instance as a special case in the mentioned articles. See [START_REF] Wormald | Models of random regular graphs[END_REF] for a survey about random regular graphs. Suppose that for all sufficiently large integers n, G n is a set of graphs with vertices 1, . . . , n. We say that G n satisfies a labelled logical limit law if for every property which can be expressed with a first-order sentence in the language of graphs, the proportion of graphs in G n which have this property converges as n → ∞. If convergence holds in the case when we count graphs only up to non-isomorphism, then we say that G n satisfies an unlabelled limit law. If the number to which the mentioned proportion converges is always 0 or 1, then one says that a zero-one law holds. Lynch [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF] has proved that a labelled logical limit law holds if we consider an infinite sequence of degree sequences ( dn ) ∞ n=1 (of the first kind mentioned above) which satisfies certain properties and for each n the graphs with vertices 1, . . . , n that have the degree sequence dn = (d n,1 , . . . , d n,n ). In particular, the main result in [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF] implies that r-regular graphs satisfy a labelled limit law, but not a zero-one law. One of the assumed properties of the sequence of degree sequences in [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF] fails in the instances that turn out to be of interest in this article, so we cannot use [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF]. Haber and Krivelevich [START_REF] Haber | The logic of random regular graphs[END_REF] have proved zero-one laws, and the absence of a limit law, for r(n)-regular graphs when r(n) is a function of the form αn or n α where 0 < α < 1; in the latter case it matters whether α is rational or not.

The case of random graphs with a fixed bound on the maximum degree, but no other constraint, has received less attention than the cases discussed so far. However, papers by Kennedy and Quintas [START_REF] Kennedy | Probability models for random f -graphs[END_REF] and Rucinski and Wormald [START_REF] Rucinski | Random graph processes with degree restrictions[END_REF][START_REF] Rucinski | Random graph processes with maximum degree 2[END_REF] are exceptions from this neglect and study the set of graphs with vertices 1, . . . , n such that every vertex has degree at most R, which we denote G n,R . They do this from the point of view of a random process which generates members of G n,R by randomly adding new edges as long as it is possible without violating the condition that the maximum degree is R. Kennedy and Quintas [START_REF] Kennedy | Probability models for random f -graphs[END_REF] stresses the importance of graphs with degree limitations from the perspective of models of physical and chemical systems and gives several references to work concerned with these aspects. Rucinski and Wormald [START_REF] Rucinski | Random graph processes with degree restrictions[END_REF] prove that with probability approaching 1 as n tends to infinity, the random process ends up with a graph with nR/2 edges. In [START_REF] Rucinski | Random graph processes with maximum degree 2[END_REF] they prove that if R = 2, then the number of k-cycles (k ≥ 3) in a graph produced by the random process has a Poisson distribution.

However, the main motivation of this article for studying G n,R comes from logic and from understanding the fine structure of H-free graphs for certain types of H. From the point of view of model theory in logic, a restriction on the maximum degree is natural and can be generalised to arbitrary relational structures via the so-called Gaifman graph (e.g. [START_REF] Ebbinghaus | Finite Model Theory[END_REF]) of the structure. Finite relational structures and firstorder logic correspond closely to relational databases and the standard query language SQL, respectively (e.g. [START_REF] Libkin | Elements of Finite Model Theory[END_REF], Chapter 1.1). Within the subfield of model theory which studies logical limit laws one may be interested in better understanding which classes of structures (e.g. graphs) have a logical limit (or even zero-one) law and which do not. When a logical limit law exists for a given logical language and collection C of finite structures it follows that, for every property P which can be expressed in that language, the proportion of structures which satisfy P stabilises as the number of elements in the structure tends to infinity. Such information may be of help when understanding the average performance of algorithms that take random members of C as input.

Another type of restriction on graphs, studied in graph theory and interesting from a model theoretic point of view, is to forbid the occurrence of subgraphs which are isomorphic to some specified graph H (or to a member of a specified set of graphs). The results of this paper are relevant for understanding H-free graphs for certain types of graphs H. Let us call a vertex v of the graph H colour critical if the removal of v from H leaves a graph with lower chromatic number than H. The criticality of v is the minimal number of edges containing v which have to be removed in order to reduce the chromatic number. Hundack, Prömel and Steger [START_REF] Hundack | Extremal graph problems for graphs with a color-critical vertex[END_REF] have proved that if H is a graph with chromatic number l + 1 (l ≥ 2) and a colour critical vertex v of criticality R + 1 and Forb n (H) is the set of H-free graphs with vertices 1, . . . , n, then the proportion of G ∈ Forb n (H) which have the following property approaches 1 as n → ∞: the vertex set can be partitioned into parts V 1 , . . . , V l such that for every i the induced subgraph with vertex set V i has maximum degree R. Hence, understanding of the asymptotic fine structure of graphs with maximum degree R helps us to understand the asymptotic fine structure of H-free graphs, for certain H. This connection is used in [START_REF] Koponen | A limit law of almost l-partite graphs[END_REF] to prove a logical limit law (but not zero-one law) for H-free graphs, when H is a complete (l + 1)-partite graph (l ≥ 2) in which one part is a singleton.

If nothing else is said then we assume that R ≥ 2 is an integer. We always consider the uniform probability distribution on G n,R . In Section 2 we study the typical degree distribution of a random G ∈ G n,R as n → ∞. We find that, as n → ∞, a random G ∈ G n,R almost surely has no vertices with degree less than R -2 and, for every ε > 0, the number of vertices with degree R -1 is almost surely between (R -ε)n and (R + ε)n, where almost surely means that the probability of the event approaches 1 as n → ∞. The number of vertices with degree R -2 has, asymptotically, a Poisson distribution. These results are summarised in Theorem 2.1. To prove it we consider multigraphs and the configuration model of Bollobás [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF][START_REF] Bollobás | Random Graphs[END_REF].

Section 3 deals with the typical structure of members of G n,R as n → ∞. The results are summarised in Theorem 3.1. Intuitively speaking, there are three types of "rare" events, which are vertices with degree R -2, short cycles and short paths with endpoints of degree R -1. They are, asymptotically, Poisson distributed and independent of each other. Moreover, these rare events typically occur far from each other. For example, the distance between any vertex with degree R -2 and any path of length 3 (say) with both endpoints of degree R -1 will almost surely be large. Also, the "semi-rare" event of being a vertex with degree R -1 almost surely occurs far from any rare event. The proofs use the configuration model of Bollobás [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF][START_REF] Bollobás | Random Graphs[END_REF] and the fact, given by Theorem 2.1, that we can restrict attention to degree sequences with certain properties.

In Section 4, we use Theorems 2.1 and 3.1 to prove a labelled logical limit law for G n,R . In the cases R = 0 and R = 1 the result is known (and trivial), in both the labelled and unlabelled context, so we need only consider the case R ≥ 2. If R ≥ 5 then we can also conclude that G n,R satisfies an unlabelled limit law, by applying a result of McKay and Wormald [START_REF] Mckay | Automorphisms of random graphs with specified vertices[END_REF], saying that in both the labelled and unlabelled cases a random member of G n,R almost surely has no non-trivial automorphism, and a general model theoretic result concerning labelled and unlabelled probabilities. We cannot apply the main result of [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF] to get the limit laws of this paper, because the degree sequences that are typical of members of G ∈ G n,R do not satisfy condition (1)(b) of [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF]. Moreover, the structural results of Sections 2 and 3 are needed for understanding logical limit laws of H-free graphs in [START_REF] Koponen | A limit law of almost l-partite graphs[END_REF].

Preliminaries, terminology and notation. See for example [START_REF] Ebbinghaus | Finite Model Theory[END_REF][START_REF] Libkin | Elements of Finite Model Theory[END_REF][START_REF] Spencer | The strange logic of random graphs[END_REF] for definitions of first-order logic, By the language of graphs we mean the first-order formulas which can be built from the vocabulary (also called signature) which consists of a binary relation symbol E (denoting the edge relation) and the identity symbol '='. More generally, a finite relational vocabulary consists of a list of relation symbols R 1 , . . . , R k (and we can assume that R 1 is '=') each with an associated arity. A structure for the language associated with this vocabulary is a tuple S = (S, R S 1 , . . . , R S 1 ) such that S is a set and R S i ⊆ S ri where r i is the arity of R i . From this point of view a graph is a structure for the language of graphs, so it has the form G = (V, E G ) where (a, b) ∈ E G implies (b, a) ∈ E G since we consider undirected graphs here. Alternatively we may, as in graph theory, view E G as the set of edges (2-subsets of V ) of G. For a first-order sentence (a formula with no free variables) ϕ in the language of graphs and a graph G, G |= ϕ is shorthand for "G satisfies ϕ". See for example [START_REF] Ebbinghaus | Finite Model Theory[END_REF][START_REF] Libkin | Elements of Finite Model Theory[END_REF] for a formal definition of '|='.

The degree of a vertex v in a graph G is denoted deg G (v), and the notation v ∼ G w means that vertices v and w are adjacent in G (which is equivalent with G |= E(v, w)). By dist G (v, w) we mean the distance from v to w in G. For functions f and g we say that f is asymptotic with g, denoted f ∼ g, if lim x→∞ f (x)/g(x) = 1. For positive integers n we sometimes use the notation [n] = {1, . . . , n}. To make notation simpler we sometimes omit explicit use of the floor function . For a set S, |S| denotes its cardinality, N 0 is the set of non-negative integers.

Distribution of degrees

For positive integers n and R, G n,R denotes the set of graphs with vertices 1, . . . , n in which the degree of every vertex is at most R.

Theorem 2.1 Suppose that R ≥ 2.

(i) The proportion of G ∈ G n,R which have no vertex with degree less than R -2 approaches 1 as n → ∞.

(ii) For every ε > 0, the proportion of G ∈ G n,R which have between (R -ε)n and (R + ε)n vertices with degree R -1 approaches 1 as n → ∞.

(iii) For every k ∈ N 0 , the proportion of G ∈ G n,R which have exactly k vertices with degree R -2

approaches (R -1) k e -(R-1) k! as n → ∞.
In other words, the number of vertices with degree R -2 has, asymptotically, a Poisson distribution with mean R -1. If

If 3 ≤ r ≤ R
lim n→∞ |{[G] : G ∈ RIG(G n )}| |{[G] : G ∈ G n }| = 1 then lim n→∞ |{[G] : G ∈ H n }| |{[G] : G ∈ G n }| = lim n→∞ |H n | |G n | ,
if any one of the last two limits exist.

We say that a graph has connectivity k if it is k-connected but not (k + 1)-connected. where G ∈ G n,R ) which have the following two properties approaches 1 as n approaches infinity:

(i) The connectivity of G is R -2 or R -1.
(ii) G is rigid.

Corollary 2.4 will be used to derive an unlabelled logical limit law in Section 4.

Multigraphs and configurations

Theorem 2.1 will be proved via the use of multigraphs and so-called configurations (defined below). The corresponding statements (of Theorem 2.1) for multigraphs are given by Lemmas 2.11, 2.12 and 2.13 below. In Section 2.2 we explain how Theorem 2.1 follows from these lemmas and from asymptotic estimates, of Bollobás [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF][START_REF] Bollobás | Random Graphs[END_REF], of probabilities of small cycles in configurations. We fix an arbitrary integer R ≥ 1.

Definition 2.5 A multigraph is an object of the form (V, f ) where f :

U → {0, 1, 2, . . .} and U = {W ⊆ V : 1 ≤ |W | ≤ 2}. If M = (V, f ) is a multigraph and v ∈ V then we define deg M (v) = 2f ({v}) + w∈V w =v f ({v, w}) and call deg M (v) the degree of v (in M). Suppose that (V, f ) is a multigraph, {v, w} ∈ U = {W ⊆ V : 1 ≤ |W | ≤ 2} and f ({v, w}) = k.
Intuitively this means that there are exactly k different edges between v and w. If v = w then it means that there are exactly k different loops which begin and end in v.

If f (W ) ≤ 1 for all W ∈ U and f (W ) = 0 whenever |W | = 1, then (V, f ) corresponds to the graph (V, E) where, for all distinct v, w ∈ V , {v, w} ∈ E if and only if f ({v, w}) = 1.

Definition 2.6

(i) Let MG n,R be the set of multigraphs with vertices 1, . . . , n such that every vertex has degree at most R.

(ii) For every sequence d = (d 0 , . . . , d R ) of non-negative integers such that

R i=0 d i = n we let MG n, d
denote the set of multigraphs with vertices 1, . . . , n such that there are exactly d i vertices with degree i for i = 0, . . . , R.

(iii) Let N (d 0 , . . . , d R ) = |MG n, d|.
Definition 2.7 Let E and F be binary relation symbols and let L c be the first-order language with vocabulary E C is an equivalence relation on C such that every E C -class has cardinality 2. The later condition implies that |C| must be even (or infinite). An E C -class of a configuration C will often be called an edge (of C). We say that

{=, E, F }. A configuration is an L c -structure C = (C, E C , F C ) such that F C is an equivalence relation on C and
C = (C, E C , F C ) is an n-configuration if F C has exactly n nonempty classes. Observe that if C = (C, E C , F C ) is a configuration, then (C, E C
) is a graph which is a complete matching (also called perfect matching), i.e. every c ∈ C is adjacent to exactly one member of C.

Definition 2.8 If m > 0 is an integer then let M(2m) denote the number of complete matchings, i.e. equivalence relations such that every class has cardinality 2, on a set with cardinality 2m.

It is easy to see that

M(2m) = 2m 2 2m -2 2 • • • 2 2 m! = (2m)! m!2 m . By Stirling's approximation, (2m)! m!2 m = 2m e m √ 2 + o(1) . (1)
Also note that for any fixed integer p we have m!/(m -p)! ∼ m p which gives

M(2m) M(2m -2p) = (2m)! m!2 m (2(m -p))! (m -p)!2 m-p ∼ (2m) p . ( 2
)
Definition 2.9

We will always assume that W 1 , . . . , W n is a sequence of disjoint sets such that

n i=1 |W i | = 2m for some integer m > 0. By C(W 1 , . . . , W n ) we denote the set of configurations C = (C, E C , F C ) such that C = n i=1 W i and W 1 , . . . , W n enumerates all the F C -classes (so if some set W i other than an F C -class appears in the sequence then W i is empty). Observe that if 2m = n i=1 |W i |, then |C(W 1 , . . . , W n )| = M(2m) = (2m)! m!2 m . ( 3
) Definition 2.10 Let C ∈ C(W 1 , . . . , W n ).
The multigraph image of C, denoted Graph(C), is the multigraph with vertices 1, . . . , n such that, for all i, j ∈ {1, . . . , n}, the number of edges between i and j is the same as the number of E C -classes which have non-empty intersection with both W i and W j . (E C -classes which are included in a single W i , if they exist, give rise to loops in Graph(C).)

Observe that for every C ∈ C(W 1 , . . . , W n ) and every i = 1, . . . , n, the degree of

i in Graph(C) is |W i |.
Moreover, if G is a multigraph with vertices 1, . . . , n such that, for i = 1, . . . , n, i has degree |W i |, then there are exactly

n i=1 |W i |! configurations C ∈ C(W 1 , . . . , W n ) such that Graph(C) = G, because Graph(C ) = Graph(C) if and only if there is an isomorphism from C to C which preserves every W i setwise. It follows that if d = (d 0 , . . . , d R ) is a sequence of non-negative integers such that R i=0 d i = n and R i=0 id i = 2m, then, using (3), we have N (d 0 , . . . , d R ) = n d 0 , . . . , d R (2m)! m!2 m R i=0 (i!) di . ( 4
)
From now on assume that d = (d 0 , . . . , d R ) is a sequence of non-negative integers such that R i=0 d i = n and R i=0 id i = 2m for some integer m > 0. We are interested in the probability that a random G ∈ MG n,R (drawn uniformly) has this degree sequence. In other words, we consider the proportion

p(d 0 , . . . , d R ) = N (d 0 , . . . , d R ) |MG n,R | = N (d 0 , . . . , d R ) N (d 0 , . . . , d R ) ,
where the sum ranges over all sequences (d 0 , . . . , d R ) of non-negative integers such that

R i=0 d i = n.
If n is even and all vertices have degree R, that is, if d i = 0 for i = 0, . . . , R -1, we get 2m = Rn and, by ( 4) and (1),

N (0, . . . , 0, n) = Rn e Rn/2 1 (R!) n √ 2 + o(1) ≥ C n 1 n Rn/2 (5)
for some constant

C 1 > 0. If n is odd, then, with d 0 = 1, d i = 0 for i = 1, . . . , R -1 and d R = n -1, we have 2m = R(n -1)
and get in a similar way

N (1, 0, . . . , 0, n -1) ≥ C n 2 n Rn/2 (6)
for some constant C 2 > 0.

Let ε > 0. We now estimate the proportion of G ∈ MG n,R for which 2m ≤ (R -ε)n. Summing over all (d 0 , . . . , d R ) for which R i=0 id i = 2m ≤ (R -ε)n gives, for large enough n and using ( 5) and [START_REF] Ebbinghaus | Finite Model Theory[END_REF],

2m≤(R-ε)n N (d 0 , . . . , d R ) ≤ 2m≤(R-ε)n n d 0 , . . . , d R (2m)! m!2 m R i=0 (i!) di ≤ (R + 1) n (R -ε)n e (R-ε)n/2 • 2 = 2(R + 1) n (R -ε)n e Rn/2 (R -ε)n e -εn/2 ≤ C 3 n -ε/2 n N, where N = N (0, . . . , 0, n) or N = N (1, 0, . . . , 0, n -1)
depending on whether n is even or odd and C 3 > 0 is a constant.

It follows that

2m≤(R-ε)n N (d 0 , . . . , d R ) |MG n,R | ≤ C 3 n -ε/2 n → 0 as n → ∞.
Therefore we will assume that 2m > (R -ε)n. Since ε > 0 is arbitrary we may in fact assume that 2m > (R -o(1))n. Since

Rn -2m = Rn - R i=0 id i = R i=0 (R -i)d i and 2m > (R -o(1))n now implies Rn -2m ≤ o(n) we get R i=0 (R -i)d i n ≤ o(1)
which in turn implies that

d i = o(n) for all i = 0, . . . , R -1. (7)
Next, we aim at showing that in the typical case we have d i = 0 for all i = 0, . . . , R -3. So until further notice we assume that R ≥ 3 since otherwise there is nothing to prove. Fix any i ≤ R -3 and suppose that d i ≥ 1. Now let

d i = d i -1,
d i+2 = d i+2 + 1 and
d j = d j for all j / ∈ {i, i + 2}.
With 2m = R j=0 jd j we have 2m = 2m + 2 (where 2m = R j=0 jd j ). Now we get, by ( 4) and ( 2),

N (d 0 , . . . , d R ) N (d 0 , . . . , d R ) = n d 0 , . . . , d R (2m)! m!2 m R j=0 (j!) dj -1 n d 0 , . . . , d R (2m )! m !2 m R j=0 (j!) d j -1 ∼ d i ! d i+2 ! d i ! d i+2 ! 1 2m R j=0 (j!) d j -dj = d i+2 + 1 d i 1 2m (i + 2)(i + 1).
As we assume that 2m > (R -o(1))n we may assume that 2m ≥ n. If i ≤ R -3 then, by [START_REF] Haber | The logic of random regular graphs[END_REF],

d i+2 = o(n) so we may assume that d i+2 + 1 ≤ f (n) where f (n) = o(n), which gives N (d 0 , . . . , d R ) N (d 0 , . . . , d R ) ≤ f (n)R 2 n .
Hence, for i ≤ R -3,

p(d 0 , . . . , d R ) ≤ R 2 f (n) n p(d 0 , . . . , d R ),
and if we sum over all (d 0 , . . . , d R ) for which

d i ≥ 1, d i+2 ≤ f (n) and 2m ≥ n, we get p(d 0 , . . . , d R ) ≤ R 2 f (n) n p(d 0 , . . . , d R ) ≤ R 2 f (n) n = o(1) (since f (n) = o(n)).
This implies that the proportion of G ∈ MG n,R which have a vertex with degree less than R -2 approaches 0 as n → ∞. Therefore we assume, from now on, that

d i = 0 for all i = 0, . . . , R -3. (8)
We also state this conclusion as:

Lemma 2.11 The proportion of G ∈ MG n,R such that G has a vertex with degree less than R -2 approaches 0 as n → ∞.

The next step is to find a lower upper bound (than in ( 7)) for d R-2 in the typical case, so we assume that R ≥ 2 until further notice. Suppose that g(n) → ∞ as n → ∞ and suppose that d R-2 ≥ g(n). We argue as before, with

i = R -2, so d R-2 = d R-2 -1, d R = d R + 1 and d j = d j if j /
∈ {R -2, R}. Just as before, and as 2m > (R -o(1))n where R ≥ 2, we get

N (d 0 , . . . , d R ) N (d 0 , . . . , d R ) ∼ d R + 1 d R-2 1 2m R(R -1) < R 2 d R-2 ≤ R 2 g(n) . Hence p(d 0 , . . . , d R ) ≤ R 2 p(d 0 , . . . , d R )/g(n) and if we sum over all (d 0 , . . . , d R ) such that d R-2 ≥ g(n) we get p(d 0 , . . . , d R ) ≤ R 2 g(n) .
Therefore we may assume that

d R-2 ≤ g(n) for every g such that lim n→∞ g(n) = ∞. (9)
The next step is to show that in the typical case

d R-1 = O( √ n). Assume that R ≥ 1 and that d R-1 ≥ 2. Let d R-1 = d R-1 -2, d R = d R + 2 and d j = d j if j / ∈ {R -1, R}.
Then 2m = 2m + 2 where 2m = R j=0 id j and

N (d 0 , . . . , d R ) N (d 0 , . . . , d R ) ∼ (d R + 1)(d R + 2) d R-1 (d R-1 -1) 1 2m R 2 ≤ (d R + 1)n d R-1 (d R-1 -1) 1 Rd R R 2 ≤ 4Rn d 2 R-2 . It follows that p(d 0 , . . . , d R ) ≤ 4Rn d 2 R-1 p(d 0 , . . . , d R ). Let P(d R-1 ≥ k) denote the proportion of G ∈ MG n,R which have at least k vertices with degree R -1.
Then for every k ≥ 2, by summation over all (d 0 , . . . , d R ) such that d R-1 ≥ k, we get

P(d R-1 ≥ k) ≤ 4Rn k 2 P(d R-1 ≥ k -2). ( 10
) If C > 2 √
R then, by iterating (10) √ n times, we get that the proportion of G ∈ MG n,R which have at least (C + 2)

√ n vertices with degree R -1 is

P d R-1 ≥ (C + 2) √ n ≤ 4Rn C √ n 2 √ n = 4R C 2 √ n → 0 as n → ∞.
Therefore we may assume, in addition to the previous assumptions ( 8) and ( 9), that

d R-1 = O( √ n). (11)
We use the notation

(n) k = n(n -1) • • • (n -k + 1)
. By equation (3.8) in [START_REF] Bender | Asymptotic methods in enumeration[END_REF], for example, we have:

If k = O( √ n), then (n) k = n k exp - k 2 2n + o(1) . (12)
To make the argument here self contained we prove [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF].

If k = O( √ n) then ln (n) k n k = ln n! (n -k)!n k = ln k-1 i=0 n -i n = ln k-1 i=0 1 - i n = k-1 i=0 ln 1 - i n ,
and for large n and i < k = O( √ n), i/n is close to 0, so by Taylor's approximation we get

k-1 i=0 ln 1 - i n = k-1 i=0 - i n + O i n 2 = - k(k -1) 2n + O k 3 n 2 = - k 2 2n + k 2n + O k 3 n 2 = - k 2 2n + o(1), since k = O( √ n).
Hence,

ln (n) k n k = -k 2 2n + o(1)
which immediately gives [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF]. Recall the exact formula (4) for N (d 0 , . . . , d R ) and remember the assumptions (8), ( 9) and [START_REF] Libkin | Elements of Finite Model Theory[END_REF]. Hence

d i = 0 for i = 0, . . . , R -3, d R-2 = o( √ n), d R-1 = O( √ n), d R = n -d R-1 -d R-2 and 2m = Rn -d R-1 -2d R-2 (
since, by definition, 2m = R i=0 id i ). By also using [START_REF] Lynch | Convergence law for random graphs with specified degree sequence[END_REF] we get

N (d 0 , . . . , d R ) = (13) = n d R-2 , d R-1 , d R • (2m)! m!2 m • 1 ((R -2)!) d R-2 ((R -1)!) d R-1 (R!) d R = (n) d R-2 +d R-1 d R-2 ! d R-1 ! • (2m)! m!2 m • (R(R -1)) d R-2 R d R-1 (R!) n = n d R-2 +d R-1 exp -(d R-2 +d R-1 ) 2 2n + o(1) d R-2 ! d R-1 ! • (2m)! m!2 m • (R(R -1)) d R-2 R d R-1 (R!) n . From 2m = Rn -d R-1 -2d R-2 and (12) it follows that (2m)! m!2 m = (Rn)! Rn/2 !2 Rn/2 • exp (d R-1 +2d R-2 ) 2 4Rn + o(1) (Rn) (d R-1 +2d R-2 )/2 . ( 14
)
By combining ( 13) and ( 14) we get

N (d 0 , . . . , d R ) = C n • (R -1) d R-2 d R-2 ! • √ Rn d R-1 d R-1 ! • ( 15
)
exp -

(d R-1 + d R-2 ) 2 2n + (d R-1 + 2d R-2 ) 2 4Rn + o(1) ,
where

C n = (Rn)! Rn/2 !2 Rn/2 • 1 (R!) n depends only on n. Note that since d R-2 = o( √ n) and d R-1 = O( √ n)
it follows that the expression 'exp(. . .)' in ( 15) is bounded as n → ∞. Lemma 2.12 (i) For every c < R the proportion of G ∈ MG n,R with less than √ cn vertices with degree R -1 approaches 0 as n → ∞.

(ii) For every c > R the proportion of G ∈ MG n,R with more than √ cn vertices with degree R -1 approaches 0 as n → ∞.

Proof: (i) Let c < R. Since there are not more than n possibilities for d R-1 , it suffices to prove that for all large enough n,

N (0, . . . , 0, d R-2 , √ cn , d R ) N (0, . . . , 0, d R-2 , √ cn + 2 n 1/4 , d R ) = c R + o(1)
2 n 1/4

• O(1).

We may assume that d R-2 = o( √ n) so by ( 12) and ( 15) the above quotient equals

( √ Rn) -2 n 1/4 • ( √ cn + 2 n 1/4 )! √ cn ! • O(1) = ( √ Rn) -2 n 1/4 • ( √ cn + 2 n 1/4 ) 2 n 1/4 = ( √ Rn) -2 n 1/4 ( √ cn + 2 n 1/4 ) 2 n 1/4 • O(1) = √ cn + 2 n 1/4 √ Rn 2 n 1/4 • O(1) = c R + o(1)
2 n 1/4

• O(1).

Part (ii), where c > R, is proved in a similar way by considering the quotient

N (0, . . . , 0, d R-2 , √ cn , d R ) N (0, . . . , 0, d R-2 , √ cn -2 n 1/4 , d R ) . 2 Lemma 2.13 For every fixed d R-2 , the proportion of G ∈ MG n,R which have exactly d R-2 vertices with degree R -2 approaches (R -1) d R-2 e -(R-1) d R-2 ! .
Proof: Let d R-2 be fixed and let c > R. We know, by ( 9) and Lemma 2.12, that the proportion of G ∈ MG n,R such that G has more than n 1/4 vertices with degree R -2 or more than √ cn vertices with degree R -1, approaches 0 as n → ∞. Therefore it suffices to prove that whenever

d R-1 ≤ √ cn, N (0, . . . , 0, d R-2 , d R-1 , d R ) n 1/4 k=0 N (0, . . . , 0, k, d R-1 , d R ) = (1 ± o(1)) (R -1) d R-2 e -(R-1) d R-2 ! .
By [START_REF] Rucinski | Random graph processes with maximum degree 2[END_REF], the above quotient equals

(1 ± o(1)) (R-1) d R-2 d R-2 ! n 1/4 k=0 (R-1) k k! = (1 ± o(1)) (R-1) d R-2 d R-2 ! e R-1 = (1 ± o(1)) (R -1) d R-2 e -(R-1) d R-2 ! . 2 2.

Configurations and graphs

In this section we explain why Lemmas 2.11, 2.12 and 2.13 also apply to graphs without multiple edges or loops. The proof of Theorem 1 in [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF] (or Theorem 2.16 in [START_REF] Bollobás | Random Graphs[END_REF]) shows the following: Fact 2.16 ( [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF][START_REF] Bollobás | Random Graphs[END_REF]) Let W 1 , . . . , W n be disjoint sets and for i = 1, . . . , R, let

d i = |{j : |W j | = i}|.
Suppose that for all i < R -2,

d i = 0 and d R-2 + d R-1 = O( √ n). (i) Then |C (W 1 , . . . , W n )| |C(W 1 , . . . , W n )| -exp - R -1 2 - (R -1) 2 4 = o(1) as n → ∞,
where the bound 'o( )' depends only on R.

(ii) From ( 3) and ( 4) it follows that if we let d = (d 0 , . . . , d R ) (with d i as above for i = 1, . . . , R and d 0 = 0), then

|G n, d| |MG n, d| -exp - R -1 2 - (R -1) 2 4 = o(1) as n → ∞,
where the bound 'o( )' depends only on R.

From part ( ii) of the fact it immediately follows that Lemmas 2.11 and 2.12 apply to graphs as well, that is, they remain true if we replace MG n,R by G n,R . To see why Lemma 2.13 also holds with G n,R in the place of MG n,R consider its proof. There we showed that

N (0, . . . , 0, d R-2 , d R-1 , d R ) n 1/4 k=0 N (0, . . . , 0, k, d R-1 , d R ) = (1 ± o(1)) (R -1) d R-2 e -(R-1) d R-2 ! . By Fact 2.16 (ii), if d = (0, . . . , 0, d R-2 , d R-1 , d R ), d R-2 + d R-1 = O( √ n), then |G n, d| = (1 ± o(1)) exp - R -1 2 - (R -1) 2 4 N (0, . . . , 0, d R-2 , d R-1 , d R ).
In the same way, for each d = (0, . . . , 0, k, d R-1 , d R ), we also get (assuming

k + d R-1 = O( √ n)) |G n, d | = (1 ± o(1)) exp - R -1 2 - (R -1) 2 4 N (0, . . . , 0, k, d R-1 , d R -k).
Therefore, the proof of Lemma 2.13 implies that, for any fixed d R-2 , the proportion of G ∈ G n,R such that G has exactly d R-2 vertices with degree R -2 approaches (R -1) d R-2 e -(R-1) d R-2 ! as n → ∞. In other words, Lemma 2.13 holds if MG n,R is replaced by G n,R . This completes the proof of Theorem 2.1.

The typical asymptotic structure

In this section we study the typical structure of large graphs with maximum degree R, where R ≥ 2 is a fixed integer. The following theorem summarises the results that will be proved. (b) If p, q ≤ k then there is no vertex v with degree less than R and p-path from v to a vertex that belongs to a q-cycle. In particular, no q-cycle contains a vertex of degree less than R.

(c) There do not exist distinct vertices v 1 , v 2 , v 3 all of which have degree at most R -1 such that for all distinct i, j ∈ {1, 2, 3} there is a path of length at most k from v i to v j .

(d) There do not exist distinct vertices v and w such that deg

G (v) ≤ R -1, deg G (w) ≤ R -2 and
there is a path of length at most k from v to w.

(ii) Let k ≥ 3 be an integer. There are positive λ 3 , . . . , λ k , µ 1 , . . . , µ k ∈ Q such that for all r 3 , . . . , r k , s 1 , . . . , s k ∈ N 0 the proportion of G ∈ G n,R which, for p = 3, . . . , k, have exactly r p p-cycles and, for p = 1, . . . , k, have exactly s p p-paths with both endpoints of degree R -1, approaches

k p=3 (λ p ) rp e -λp r p ! k p=1 (µ p ) sp e -µp s p ! as n → ∞.
Moreover, the mentioned proportion approaches this value independently of the number of vertices with degree R -2.

(iii) If R ≥ 3 then for every k ∈ N 0 the proportion of G ∈ G n,R such that G has a connected component with at most k vertices approaches 0 as n → ∞.

Note that part (ii) of the theorem states that if X p is the number of p-cycles, for p = 3, . . . , k, and Y p is the number of p-paths with endpoints of degree R -1, for p = 1, . . . , k, then the random variables X 3 , . . . , X p , Y 1 , . . . , Y p are, asymptotically, independent Poisson variables with means λ 3 , . . . , λ k , µ 1 , . . . , µ k , respectively, which are described in detail by Lemma 3.7. If one omits the consideration of short paths with endpoints of degree R -1 in part (ii), then the resulting statement is a straightforward consequence of Theorem 2.1 and either one of Theorem 1 in [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF], (the proof of) Theorem 2.16 in [START_REF] Bollobás | Random Graphs[END_REF], or Corollary 1 in [START_REF] Wormald | The asymptotic distribution of short cycles in random regular graphs[END_REF]. However, knowing the distribution of short paths with endpoints of degree R -1 is necessary in the proof of the limit law in Section 4.

Graphs with a given degree sequence

Fix an integer R ≥ 2. By Theorem 2.1,

• the proportion of G ∈ G n,R without vertices with degree less than R -2 approaches 1 as n → ∞,

• the number of vertices of G ∈ G n,R with degree R -2 has a Poisson distribution, asymptotically, and

• for every ε > 0, the proportion of G ∈ G n,R which have between (R -ε)n and (R + ε)n vertices with degree R -1 approaches 1 as n → ∞.

Therefore, there are ε n and δ n such that lim n→∞ ε n = lim n→∞ δ n = 0, the proportion of G ∈ G n,R without vertices of degree 0, with at most n 1/4 vertices with degree R -2 and with between (R -

δ n )n and (R + δ n )n vertices with degree R -1 is at least 1 -ε n . Let G n,R be the set of all G ∈ G n,R
such that G has no vertices of degree less than R -2, at most n 1/4 vertices of degree R -2 and between

(R -δ n )n and (R + δ n )n vertices with degree R -1. It follows that |G n,R | |G n,R | → 1 as n → ∞.
Since the number of edges of G = (V, E G ) equals 1

(i) = d i for i = 1, . . . , n. (G n,R ( d) is different from G n, d in Section 2.) A priori we do not know if G n,R (
d) is non-empty for every d such that n i=1 d i is even. But for such degree sequences d as we will consider (satisfying ( 16) below) it follows from Fact 2.16 above that G n,R ( d) is indeed non-empty if, in addition, n i=1 d i is even and n is sufficiently large. Bollobás [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF][START_REF] Bollobás | Random Graphs[END_REF] gives asymptotic estimates of |G n,R ( d)|. Now suppose that σ n are positive numbers such that lim n→∞ σ n = 0, that P is a property of graphs and that 0 < c < 1. Moreover, assume that whenever n is large enough and

d = (d 1 , d 2 , . . . , d n ) satisfies that R -2 ≤ d i ≤ R for all i = 1, . . . , n, |{i : d i = R -2}| ≤ n 1/4 and ( 16
) (R -δ n )n ≤ |{i : d i = R -1}| ≤ (R + δ n )n and G n,R ( d) = ∅, then the proportion of G ∈ G n,R (
|P n | = d |P n ( d)| ≥ (c -σ n ) d |G n,R ( d)| = (c -σ n )|G n,R | and in a similar way |P n | ≤ (c + σ n )|G n,R |,
where the sums range over all d which satisfy ( 16), so c-σ n ≤ |P n | |G n,R | ≤ c+σ n . It follows that the proportion of G ∈ G n,R which have property P approaches c as n → ∞ and hence also the proportion of G ∈ G n,R which have property P approaches c as n → ∞. To summarise the argument, we have: Conclusion. To prove that the proportion of G ∈ G n,R which have a property P approaches c as n → ∞, independently of the number of vertices with degree R -2 in G, it suffices to prove that for every degree sequence d which satisfies [START_REF] Spencer | The strange logic of random graphs[END_REF] and such that

Proof of Theorem 3.1

The lemmas of this section prove the different parts of Theorem 3.1. Let R ≥ 2 be an integer. Until the proof of Lemma 3.7 is finished, we assume that W 1 , . . . , W n are disjoint sets,

d i = |W i |, n i=1 d i = 2m
and that ( 16) holds. This implies that 2m ∼ Rn.

As we observed in Sections 2.1 and 2.

2, if d = (d 1 , . . . , d n ), then G n,R ( d) can be identified with {Graph(C) : C ∈ C (W 1 , . . . , W n )}.
By Fact 2.16 and the discussion in Section 3.1, it follows that in order to prove that the proportion of G ∈ G n,R with property P approaches c as n → ∞, it now suffices to prove that

C ∈ C (W 1 , . . . , W n ) : Graph(C) has P |C (W 1 , . . . , W n )| -c = o(1) as n → ∞,
where the bound o( ) depends only on P and R.

Lemma 3.2 For all integers p ≥ 1 and q ≥ 3, the proportion of G ∈ G n,R which have a vertex v of degree less than R and a p-path from v to a vertex in a q-cycle approaches 0 as n → ∞. It follows that the proportion of G ∈ G n,R which have a vertex v of degree less than R such that v belongs to a q-cycle approaches 0 as n → ∞.

Proof: Let p ≥ 1 and q ≥ 3. If C ∈ C (W 1 , . . . , W n ) and Graph(C) has a vertex W i with degree less than R and a p-path from W i to a vertex in a q-cycle, then |W i | < R and there are W j , a p-path e 1 , . . . , e p (of C) and a q-cycle e 1 , . . . , e q (of C) such that e 1 ∩ W i = ∅, e p ∩ W j = ∅ and e 1 ∩ W j = ∅. If W i belongs to a q-cycle of Graph(C), then let W j = W i and note that a p-path as e 1 , . . . , e p of C as above need not exist, but the argument below (with p = 0 and finding at most q -1 other F -classes than W i ) shows that the corresponding quotient (below) still approaches 0 as n → ∞; this will prove the second statement of the lemma. Therefore it suffices to prove that the proportion of C ∈ C(W 1 , . . . , W n ) such that for some W i with |W i | < R there are W j , a p-path e 1 , . . . , e p and a q-cycle e 1 , . . . , e q such that e 1 ∩ W i = ∅, e p ∩ W j = ∅ and e 1 ∩ W j = ∅ approaches 0 as n → ∞.

By assumption [START_REF] Spencer | The strange logic of random graphs[END_REF] we can choose W i with cardinality less than R in at most n 1/4 + (R + δ(n))n ways, where δ(n) → 0 as n → ∞. A p-path e 1 , . . . , e p and a q-cycle e 1 , . . . , e q such that e p ∩ W j = ∅ and e 1 ∩ W j = ∅ for some j can intersect at most p -1 + q different F -classes other than W i . Hence the at most p + q -1 F -classes other than W i which are going to include the union of the p-path and q-cycle as above can be chosen in at most n p+q-1 ways. Then the 2(p + q) elements which are going to form the union of the edges e 1 , . . . , e p , e 1 , . . . , e q can be chosen in no more than (p + q)R 2(p+q) ways. Then a complete matching on these 2(p + q) elements (that is, non-intersecting edges e 1 , . . . , e p , e 1 , . . . , e q ) can be chosen in M(2(p + q)) ways. Finally, a complete matching on the remaining 2m -(2p + 2q) elements can be chosen in M(2m -(2p + 2q)) ways. Therefore, there is a constant α > 0 depending only on p, q and R such that, for all sufficiently large n, the proportion of C ∈ C(W 1 , . . . , W n ) for which there are W i with |W i | < R, W j , a p-path e 1 , . . . , e p and a q-cycle e 1 , . . . , e q such that e 1 ∩ W i = ∅, e p ∩ W j = ∅ and e 1 ∩ W j = ∅ is at most

α √ n n p+q-1 M(2m -2(p + q)) M(2m) ∼ α n p+q-1/2 (2m) p+q ∼ α n p+q-1/2 (Rn) p+q = α n -1/2 R p+q → 0 as n → ∞,
where (2) was used in the first asymptotic identity. 2

The next lemma is a well known result in the case of R-regular graphs [START_REF] Wormald | Models of random regular graphs[END_REF], and can be proved in a similar way in that case.

Lemma 3.3 If H is a graph with more edges than vertices, then the proportion of G ∈ G n,R which have a subgraph that is isomorphic to H approaches 0 as n → ∞.

Proof: Let H be a graph with p > 0 vertices and q > p edges.

If C ∈ C(W 1 , . . . , W n ) (so in particular if C ∈ C (W 1 , . . . , W n ))
and Graph(C) has a subgraph H which is isomorphic to H, then there are W i1 , . . . , W ip and p + 1 edges of C (i.e. E-classes) e 1 , . . . , e p+1 such that e j ⊆ W i1 ∪ . . . ∪ W ip for j = 1, . . . , p+ 1. Hence it is sufficient to prove that the proportion of C ∈ C(W 1 , . . . , W n ) such that there are W i1 , . . . , W ip and p + 1 edges of C, e 1 , . . . , e p+1 , such that e j ⊆ W i1 ∪ . . . ∪ W ip for j = 1, . . . , p + 1 approaches 0 as n → ∞.

We can choose W i1 , . . . , W ip in at most n p ways, and then choose p + 1 disjoint 2-subsets of

p j=1 W ij in at most α = Rp 2 Rp-2 2 • • • Rp-2p 2
ways. The remaining 2m -2(p + 1) elements can be completely matched in M(2m-2(p+1)) ways. Consequently, the proportion of C ∈ C(W 1 , . . . , W n ) such that there are W i1 , . . . , W ip and p + 1 edges of C, e 1 , . . . , e p+1 , such that e j ⊆ W i1 ∪ . . . ∪ W ip for j = 1, . . . , p + 1 is at most

α n p M(2m -2(p + 1)) M(2m) ∼ α n p (2m) p+1 ∼ αn p (Rn) p+1 = α R p+1 n → 0 as n → ∞. 2
Remark 3.4 Observe that Lemma 3.3 implies the following: For all integers p ≥ 0 and q ≥ 3, the proportion of G ∈ G n,R for which there are 3 ≤ i, j ≤ q, an i-cycle and a different j-cycle within distance p of each other, approaches 0 as n → ∞.

Lemma 3.5 For every integer p > 0, the proportion of G ∈ G n,R that have three distinct vertices v 1 , v 2 , v 3 with degree less than R such that for all distinct i, j ∈ {1, 2, 3} there is a path of length at most p from v i to v j , approaches 0 as n → ∞.

Proof: Let p be a positive integer. It suffices to prove that, for every choice of positive integers p 1 , p 2 ≤ p, the proportion of C ∈ C(W 1 , . . . , W n ) with the following property approaches 0 as n → ∞:

( * ) There are W i1 , W i2 , W i3 with |W i1 |, |W i2 |, |W i3 | < R such
that there is a p 1 -path with endpoints in W i3 and W i1 and a p 2 -path with endpoints in W i3 and W i2 .

Let c > R. By Assumption [START_REF] Spencer | The strange logic of random graphs[END_REF], for all large enough n there are at most √ cn F -classes W i with cardinality less than R, so W i1 , W i2 , W i3 can be chosen in at most (cn) 3/2 ways. The other p 1 + p 2 -2 F -classes which the p 1 -path and p 2 -path are going to intersect can be chosen in at most n p1+p2-2 ways. The union of all edges in the two paths will contain 2(p 1 + p 2 ) elements, which can be chosen in no more than (p 1 + p 2 + 1)R 2(p1+p2) ways, since they belong to the already chosen F -classes. A complete matching (forming two paths) on these elements can be chosen in no more than M(2(p 1 + p 2 )) ways, and a complete matching on the remaining 2m -2(p 1 + p 2 ) elements can be chosen in M(2m -2(p 1 + p 2 )) ways. Hence, for some constant α depending only on p 1 , p 2 and R, the proportion of C ∈ C(W 1 , . . . , W n ) that satisfy ( * ) is at most

αn 3/2 n p1+p2-2 M(2m -2(p 1 + p 2 )) M(2m) ∼ αn p1+p2-1/2 (2m) p1+p2 ∼ αn p1+p2-1/2 (Rn) p1+p2 = αn -1/2 R p1+p2 → 0 as n → ∞. 2
Lemma 3.6 For every integer p > 0, the proportion of G ∈ G n,R which have vertices v and w such that

deg G (v) ≤ R -2, deg G (w) ≤ R -
|W i2 | ≤ R -1 in at most n 1/4 • ( (R + δ(n))n + n 1/4 ) = R + δ(n) • n 3/4 + √ n ways.
The p -1 Fclasses other than W i1 and W i2 which the p-path is going to intersect can be chosen in at most n p-1 ways. The number of ways in which 2p elements from W i1 , W i2 and the other chosen F -classes can be chosen is bounded by a constant depending only on p and R; the same is true for the number of ways of choosing a p-path from these elements. Finally, a complete matching on the remaining 2m -2p elements can be chosen in M(2m -2p) ways. So the proportion of C ∈ C(W 1 , . . . , W n ) with the described property is, for some constant α depending only on p and R, at most . In other words, if X p is the number of p-cycles and Y p is the number of p-paths with both endpoints of degree R -1, then the random variables X p , p = 3, . . . , k and Y p , p = 1, . . . , k, are asymptotically independent Poisson variables with mean λ p and µ p , respectively. Moreover, the random variables X p , p = 3, . . . , k, and Y p , p = 1, . . . , k, are asymptotically independent of the (asymptotically Poisson distributed) number of vertices with degree R -2.

αn 3/4 n p-1 M(2m -2p) M(2m) ∼ αn p-1/4 (2m) p ∼ αn p-1/4 (Rn) p = αn -1/4 R p → 0 as n → ∞. 2
Proof: Let k ≥ 3. The last statement of the lemma will follow from the argument below, because the only thing regarding the number of vertices with degree R -2, or in the context of configurations, the number of F -classes of cardinality R -2, is that this number is at most n 1/4 ; so the limit to be proved is independent of the number of vertices (F -classes) with degree (cardinality) R -2. For p = 1, . . . , k, let the random variable X p be the number of p-cycles of a configuration C ∈ C(W 1 , . . . , W n ) and let the random variable Y p be the number of p-paths (of C) with both endpoints in F -classes of cardinality R -1. For p = 1, . . . , k, let

λ p = (R -1) p 2p and µ p = (R -1) p+1 2 .
We will prove:

Claim. X 1 , . . . , X k , Y 1 , . . . , Y k are asymptotically independent Poisson variables with mean λ 1 , . . . , λ k , µ 1 , . . . , µ k , respectively.

By Fact 2.16 (i), the probability that X 1 = X 2 = 0 approaches exp(-λ 1 -λ 2 ) as n → ∞, and therefore (using part ( ii) of the same fact) the lemma follows from the claim. Actually the argument that follows proves Fact 2.16 ( i), but also considers the random variables Y 1 , . . . , Y k of the lemma, which we must take into account when proving a logical limit law. Recall the notation (x) i = x(x -1) . . . (x -i + 1). Note that the random variable

Z = (X 1 ) r1 (X 2 ) r2 . . . (X k ) r k (Y 1 ) s1 (Y 2 ) s2 . . . (Y k ) s k
is the number of ordered 2k-tuples without repetition consisting of (from left to right) r 1 1-cycles, r 2 2-cycles, . . ., r k k-cycles, s 1 1-paths with both endpoints in F -classes of cardinality R -1, . . . and s k k-paths with both endpoints in F -classes of cardinality R -1. By Theorem 1.23 in [START_REF] Bollobás | Random Graphs[END_REF], to prove the claim it suffices to prove that

E(Z) - k p=1 (λ p ) rp (µ p ) sp = o(1) as n → ∞, (17)
where E( ) denotes the expected value and the bound 'o( )' depends only on k, R, r 1 , . . . , r k and s 1 , . . . , s k . Indeed, in the argument we never use any other properties of the degree sequence d = (d 1 , . . . , d n ) than those stated in [START_REF] Spencer | The strange logic of random graphs[END_REF], which hold for all degree sequences that we consider. Let Z be the number of ordered 2k-tuples (A 1 , . . . , A 2k ) without repetition as counted by Z above, but with the extra condition that there is no W i such that for two distinct entries A j , A j (j = j) and edges e j ∈ A j and e j ∈ A j , e j ∩W i = ∅ and e

j ∩W i = ∅. Let Z = Z -Z , so Z = Z +Z and E(Z) = E(Z )+E(Z ).
Let C p (n) be the number of ways to choose a p-cycle (a matching on a 2p-subset of W 1 ∪ . . . ∪ W n which forms a p-cycle), so we have

C p (n) ≤ R(R -1)n p 2p . (18)
Then let P p (n) be the number of ways to choose a p-path with both endpoints in F -classes with cardinality R -1, so by assumption [START_REF] Spencer | The strange logic of random graphs[END_REF],

P p (n) ≤ (R -1) 2 (R + δ n )n R(R -1)n p-1 2 (19)
∼ (R -1) R(R -1)n p 2 as n → ∞.
For every A ⊂ n i=1 W i , let C p (n, A) and P p (n, A) be defined as C p (n) and P p (n) but with the extra condition that no chosen edge (E-class) has non-empty intersection with A. Let t = k p=1 (pr p + ps p ) and let

C p (n, t) = min C p (n, A) : A ⊆ n i=1 W i , |A| = 2t , and P p (n, t) = min C p (n, A) : A ⊆ n i=1 W i , |A| = 2t . Let f (n) = n -(R + δ n )n -n 1/4 -2t. From (16) we get C p (n, t) ≥ R(R -1)f (n) p 2p ∼ R(R -1)n p 2p and (20)
P p (n, t) ≥ (R -1) 2 (R -δ n )n -2t 2 2 R(R -1)f (n) p-1 (21)
∼ (R -1) R(R -1)n p 2 as n → ∞.
We have

k p=1 C p (n, t) rp P p (n, t) sp ≤ Z ≤ k p=1 C p (n) rp P p (n) sp ,
so by ( 18), ( 19), ( 20) and (21) we get

Z ∼ k p=1 R(R -1)n p 2p rp (R -1) R(R -1)n p 2 sp . (22)
For every tuple (A 1 , . . . , A 2k ) that is being counted by Z , we have 2k p=1 A p = 2t and for every A ⊆ n i=1 W i with |A| = 2t and every complete matching on A, the proportion of configurations in C(W 1 , . . . , W n ) which have this matching on A is

M(2m -2t) M(2m) ∼ (2m) -t ∼ (Rn) -t .
From this and (22) and recalling that t = k p=1 (pr p + ps p ), we get

E(Z ) ∼ (Rn) -k p=1 (prp+psp) k p=1 R(R -1)n p 2p rp (R -1) R(R -1)n p 2 sp = k p=1 (R -1) p 2p rp (R -1) p+1 2 sp = k p=1 (λ p ) rp (µ p ) sp .
By ( 18), ( 19), ( 20) and ( 21), E(Z ) -k p=1 (λ p ) rp (µ p ) sp = o(1) as n → ∞ where the bound depends only on R, k, r 1 , . . . , r k and s 1 , . . . , s k .

Since Z = Z + Z it now suffices to prove that lim n→∞ E(Z ) = o(1), where the bound depends only on R, k, r 1 , . . . , r k and s 1 , . . . , s k , because this together with the conclusion above implies the statement of [START_REF] Wormald | The asymptotic connectivity of labelled regular graphs[END_REF]. But Z > 0 means that at least one of the following conditions holds: (a) For some q ≤ t there are W i1 , . . . , W iq and edges e 1 , . . . , e q+1 such that e j ⊆ W i1 ∪ . . . ∪ W iq for j = 1, . . . , q + 1.

(b) For some q, q ≤ t and some W i with |W i | < R there are W j , a q-path e 1 , . . . , e q and q -cycle e 1 , . . . , e q such that e 1 ∩ W i = ∅, e q ∩ W j = ∅ and e 1 ∩ W j = ∅.

Theorem 4.1 Let R be a non-negative integer.

(i) Suppose that R ≥ 0. For every first order sentence ϕ in the language of graphs, there is c ∈ [0, 1] such that

lim n→∞ {G ∈ G n,R : G |= ϕ} G n,R = c.
(ii) Suppose that 0 ≤ R ≤ 1 or R ≥ 5. For every first-order sentence ϕ in the language of graphs, there is c ∈ [0, 1] such that

lim n→∞ {[G] : G ∈ G n,R and G |= ϕ} {[G] : G ∈ G n,R } = lim n→∞ {G ∈ G n,R : G |= ϕ} G n,R = c.
In other words, for every R ≥ 0, finite graphs with maximum degree R satisfy a labelled limit law for first-order logic. If 0 ≤ R ≤ 1 or R ≥ 5 then we also have an unlabelled limit law. If R = 0 or R = 1 then we have a zero-one law in both the labelled an unlabelled case (as the proof below will show), that is, the number c in the theorem is either 0 or 1 for every ϕ. If R ≥ 2 then we do not have a zero-one law, because (for example) the non-existence of a vertex with degree R -2, which can be expressed with a sentence in first-order logic, holds with asymptotic probability e -(R-1) , by Theorem 2.1. This paper does not settle the question of whether or not G n,R has an unlabelled limit law for R = 2, 3, 4.

Proof of Theorem 4.1

If R = 0 then |G n,R | = 1 for every n, so the theorem is trivial in this case. If R = 1 then there are only two isomorphism types of connected components, singletons and two vertices connected to each other, so by Example 7.15 in [START_REF] Compton | A logical approach to asymptotic combinatorics I. First order properties[END_REF] the theorem follows, both in the labelled and unlabelled case. (In this simple case one can of course also argue directly, without reference to [START_REF] Compton | A logical approach to asymptotic combinatorics I. First order properties[END_REF] which has much wider applicability.) For the rest of the proof we assume that R ≥ 2. We will prove that for every first-order sentence ϕ, the proportion |{G ∈ G n,R : G |= ϕ}| |G n,R | converges as n → ∞; so we get part (i) of the theorem for all R ≥ 2. By Corollary 2.4 and Theorem 2.3 we then get part (ii) for R ≥ 5, because in Theorem 2.3 we can, for any sentence ϕ, let H n be the set of G ∈ G n,R such that G |= ϕ.

Every first-order sentence has a quantifier rank (also called quantifier depth) (see [START_REF] Ebbinghaus | Finite Model Theory[END_REF][START_REF] Libkin | Elements of Finite Model Theory[END_REF][START_REF] Spencer | The strange logic of random graphs[END_REF] for example) which is a non-negative integer. Therefore it suffices to show that for every k > 0 and every first-order sentence ϕ with quantifier rank at most k, the quotient |{G ∈ G n,R : G |= ϕ}| |G n,R | converges as n → ∞. So we fix an arbitrary integer k ≥ 3. Definition 4.2 Let m = 5 k+1 . For all q, r 3 , . . . , r m , s 1 , . . . , s m ∈ {0, 1, . . . , k}, define X n (q, r 3 , . . . , r m , s 1 , . . . , s m ) to be the set of all G ∈ G n,R such that the following holds:

1. There are no vertices with degree less that R -2, 2. If q < k then there are exactly q vertices with degree R -2 and if q = k then there are at least k vertices with degree R -2.

3. There are at least m vertices with degree i for i = R -1, R.

4. For p = 3, . . . , m, if r p < k then there are exactly r p p-cycles and if r p = k then there are at least k p-cycles.

5. For p = 1, . . . , m, if s p < k then there are exactly s p p-paths with both endpoints of degree R -1 and if s p = k then there are at least k p-paths with both endpoints of degree R -1. Hence it is enough to prove that for all q, r 3 , . . . , r m , s 1 , . . . , s m ∈ {0, 1, . . . , k}, if G, H ∈ X n (q, r 3 , . . . , r m , s 1 , . . . , s m ), then G and H satisfies exactly the same sentences of quantifier rank at most k. To show that G and H satisfies exactly the same sentences of quantifier rank at most k it suffices to prove that Duplicator has a winning strategy for the Ehrenfeucht-Fraïssé game in k steps on G and H (e.g. [START_REF] Ebbinghaus | Finite Model Theory[END_REF], Theorem 2.2.8, or similar results in [START_REF] Libkin | Elements of Finite Model Theory[END_REF][START_REF] Spencer | The strange logic of random graphs[END_REF]). So we fix q, r 3 , . . . , r m , s 1 , . . . , s m ∈ {0, 1, . . . , k} and let G, H ∈ X n (q, r 3 , . . . , r m , s 1 , . . . , s m ).

For any vertex v of G and l ∈ N 0 we let B G (v, l) be the set of vertices w such that dist G (v, w) ≤ l; and similarly for H. Let a Poisson object of G or H denote any one of

• a vertex with degree R -2, or

Definition 2 .

 2 [START_REF] Rucinski | Random graph processes with degree restrictions[END_REF] Let C = (C, E C , F C ) be a configuration and let p ≥ 1 be an integer. By a path (of C) from a ∈ C to b ∈ C of length p, or p-path from a to b, we mean sequence of p distinct edges (i.e. E C -classes) e 1 , . . . , e p such that there areF C -classes W 1 , . . . , W p+1 such a ∈ e 1 ∩ W 1 , b ∈ e p ∩ W p+1 , W i = W j if i = j and i = 1 or if i = j and j = p + 1 (but we allow that W 1 = W p+1) and, for i = 1, . . . , p, e i contains a member of W i and a member of W i+1 . In the described situation we call a and b the endpoints of the path. By a p-cycle (of C) we mean a p-path from a to b for some a and b such that (a, b) ∈ F C ; or in other words, a p-path from a to b where a, b ∈ W for some F C -class W . Recall Definition 2.9 of C(W 1 , . . . , W n ) and Definition 2.10 about the multigraph image Graph(C) of a configuration C. It is easy to see that that if C ∈ C(W 1 , . . . , W n ) and C has no p-cycle for p = 1, 2, then Graph(C) has no loops or multiple edges. Definition 2.15 By C (W 1 , . . . , W n ) we denote the set of configurations C ∈ C(W 1 , . . . , W n ) which have no p-cycle for p = 1, 2.

Theorem 3 . 1

 31 Let R ≥ 2 be an integer. (i) For every integer k > 0 the proportion of graphs G ∈ G n,R which have properties (a)-(d) below approaches 1 as n → ∞: (a) If p ≤ k then G has no subgraph H with exactly p vertices and more than p edges. It follows that whenever p 1 , p 2 ≥ 3 and p 1 + p 2 + p 3 ≤ k, then G does not have a p 1 -cycle and a p 2 -cycle such that there is a p 3 -path from a vertex in the first cycle to a vertex in the second cycle.

2 v∈V

 2 deg G (v) it follows that v∈V deg G (v) must be even. For every positive n ∈ N 0 and sequence of integers d = (d 1 , d 2 , . . . , d n ) such that 0 ≤ d i ≤ R for all i = 1, . . . , n and n i=1 d i is even, let G n,R ( d) be the set of graphs G with vertices 1, . . . , n such that deg G

n

  i=1 d i is even, the proportion of G ∈ G n,R ( d) which has P , |P n ( d)| |G n,R ( d)|, approaches c as n → ∞ and |P n ( d)| |G n,R ( d)| -c is bounded by a function which tends to zero and depends only on P and R.

Lemma 3 . 7

 37 Let k ≥ 3 be an integer and let r 3 , . . . , r k , s 1 , . . . , s k ∈ N 0 . Then the proportion of G ∈ G n,R which, for p = 3, . . . , k, have exactly r p p-cycles and, for p = 1, . . . , k, have exactly s p p-paths with both endpoints of degree R -1, approachesk p=3 (λ p ) rp e -λp r p ! k p=1 (µ p ) sp e -µp s p ! as n → ∞,where λ p = (R-1) p 2p and µ p = (R-1) p+1 2

6 .

 6 The distance is at least 5 k+2 between (a) any vertex with degree R -2 and any (other) vertex of degree at most R -1, (b) any vertex with degree at most R -1 and any cycle of length at most m, (c) any two different cycles of length at most m, and (d) any two different paths of length at most m such that both endpoints of both paths have degree R -1.

7 . 2 .

 72 If R ≥ 3 then every connected component has at least m vertices. Let P k (x, µ) = µ x e -µ k, and let λ p = (R-1) p 2p and µ p = (R-1) p+1 By Theorems 2.1 and 3.1 and Lemma 3.7, lim n→∞ |X n (q, r 3 , . . . , r m , s 1 , . . . , s m )| |G n,R | = P k (q, R -1) m p=3 P k (r p , λ p ) m p=1 P k (s p , µ p ) .

  and d = (d r , . . . , d R ) is a sequence of non-negative integers summing to n, then let G n, For every positive integer n, let H n ⊆ G n be sets of graphs with vertices 1, . . . , n. Suppose that, for every n, if G ∈ H n , H has vertices 1, . . . , n and is isomorphic to G, then H ∈ H n ; and if G ∈ G n , H has vertices 1, . . . , n and is isomorphic to G, then H ∈ G n . For every n and G ∈ G n , let[G] denote the equivalence class to which G belongs with respect to the isomorphism relation on G n . Let RIG(G n ) be the set of G ∈ G n which are rigid.

	d
	be the set of all graphs G with vertices 1, . . . , n such that, for i = r, . . . , R, G has exactly d i vertices with
	degree i. Wormald (Theorem 1 in [17]) and McKay and Wormald (Corollaries 3.8 and 3.10 in [13]) have
	proved the following:
	Theorem 2.2 ([17, 13]) If 3 ≤ r ≤ R and d = (d r , . . . , d R ) is a sequence of non-negative integers
	summing to n, then
	(i) the number of r-connected G ∈ G n, d is |G n, d| 1 -O n 2-r where O( ) denotes a bound depend-
	ing only on R, and
	(ii) the expected number of nontrivial automorphisms of a random G ∈ G n, d is O(n 2-r ) where O( )
	denotes a bound depending only on R.
	Statement (i) is true also if we count graphs in G n, d only up to isomorphism, or in other words, if we consider unlabelled graphs with n vertices and degree sequence d.
	Let us call a graph rigid if it has only one automorphism, the trivial one. Theorem 4.3.4 in [6], if stated in
	the context of graphs, says the following.
	Theorem 2.3 ([6])

  Suppose that R ≥ 5. The proportion of graphs G ∈ G n,R (or of isomorphism classes [G]

	(By k-connected we
	mean k-vertex connected.) By combining Theorems 2.1, 2.2 and 2.3 we get the following information
	about typical members of G n,R for large n.
	Corollary 2.4

  1 and a p-path from v to w approaches 0 as n → ∞.Proof: Let p > 0. It suffices to prove that the proportion of C ∈ C(W 1 , . . . , W n ) which have F -classes W i1 , W i2 such that |W i1 | ≤ R -2 and |W i2 | ≤ R -1and a p-path starting in W i1 and ending in W i2 approaches 0 as n → ∞. By Assumption[START_REF] Spencer | The strange logic of random graphs[END_REF], one can choose W i1 and W i2 such that |W i1 | ≤ R -2 and

Acknowledgements

I thank Svante Janson and Nicholas Wormald for helpful comments and discussions. In particular, Janson suggested the proof of Theorem 2.1 which is presented here. (My proof first obtained some rough estimates by counting arguments and then applied a known asymptotic formula for graphs with given degree sequence, which, however, involved rather long and tedious calculations.) Also, thanks to the anonymous referee for careful reading and helping me to remove various mistakes.

(c) There are distinct W i1 , W i2 , W i3 with |W i1 |, |W i2 |, |W i3 | < R and for every pair j, j ∈ {1, 2, 3} such that j = j a path of length at most t from some a ∈ W ij to some b ∈ W i j .

From the proofs of Lemmas 3.2, 3.3 and 3.5, it follows that the proportion of C ∈ C(W 1 , . . . , W n ) satisfying any of (a), (b) or (c) approaches 0 as n → ∞, and in each case the convergence is bounded by a function depending only on R, k, r • There is no subgraph with p vertices and more than p edges.

• There do not exist distinct vertices v i , i = 1, 2, 3, all three with degree R -1 such that for all distinct i, j ∈ {1, 2, 3} there is a path of length at most p from v i to v j .

• There do not exist distinct vertices v and w both of degree R -2 and a path of length at most p from v to w.

• No vertex has degree less than R -2.

Therefore it suffices to show that if G ∈ G R has a connected component with exactly p vertices, then one of the above properties fail for G. Recall the assumption that R ≥ 3 and suppose that H ⊆ G is a connected component with exactly p vertices. If p = 1 then the unique vertex in H has degree 0 < R -2, so G does not have the last property above. If p = 2 then the two vertices of H have degree 1 ≤ R -2 in G, so the third or fourth property fails. If p = 3 then the three vertices of H have degree at most 2 ≤ R -1 in G, so G does not have the second property. Now suppose that p ≥ 4. If the last three properties hold, then the number of edges in H is at least

where the last inequality holds for all p ≥ 4 (by induction or differentiation). Hence H has more than p edges, so G does not have the first property. 2

Note that Lemma 3.8 is false for R = 2, because if R = 2 then every 3-cycle (say) is a connected component and the proportion of G ∈ G n,2 with at least one 3-cycle converges to a positive number, by Lemma 3.7, as n → ∞. In the case R ≥ 5 Lemma 3.8 is a consequence of Corollary 2.4.

First-order limit laws

Recall that G n,R denotes the set of undirected graphs with vertices 1, . . . , n such that every vertex has degree at most R.

is an isomorphism such that f i (v j ) = w j for j = 1, . . . , i. Then there is w i+1 ∈ {1, . . . , n} (or v i+1 ∈ {1, . . . , n}) such that the same statement holds with 'i + 1' in place of 'i'.

Proof: Suppose that i < k, v 1 , . . . , v i , w 1 , . . . , w i ∈ {1, . . . , n} and that

is an isomorphism such that f i (v j ) = w j for j = 1, . . . , i. By symmetry it is enough to consider the case when Spoiler chooses v i+1 in G.

) and let f i+1 be the restriction of

Then there is u ∈ B G v i+1 , 5 k-i-1 such that the distance (in G) from u to v j is at least 5 k-i for all j = 1, . . . , i. It follows that for every a ∈ B G v i+1 , 5 k-i-1 and every j = 1, . . . , i, the distance from a to v j is at least

r 3 , . . . , r m , s 1 , . . . , s m ) and f i is an isomorphism it follows from Observation 4.3, for large enough n, that there are w i+1 and an isomorphism

such that f i+1 (v i+1 ) = w i+1 and dist H (w i+1 , u) ≥ 2 for every u ∈ i j=1 B H w i , 5 k-i . Then the desired isomorphism f i+1 is obtained by letting


Hossein Hajiabolhassan

Farokhlagha Moazami

Secure Frameproof Codes Through Biclique Covers

Keywords: cover-free family, secure frameproof code, biclique cover, Hadamard matrix

For a binary code Γ of length v, a v-word w produces by a set of codewords {w 1 , . . . , w r } ⊆ Γ if for all i = 1, . . . , v, we have wi ∈ {w 1 i , . . . , w r i }. We call a code r-secure frameproof of size t if |Γ| = t and for any v-word that is produced by two sets C1 and C2 of size at most r, then the intersection of these sets is non-empty. A d-biclique cover of size v of a graph G is a collection of v complete bipartite subgraphs of G such that each edge of G belongs to at least d of these complete bipartite subgraphs. In this paper, we show that for t ≥ 2r, an r-secure frameproof code of size t and length v exists if and only if there exists a 1-biclique cover of size v for the Kneser graph KG(t, r) whose vertices are all r-subsets of a t-element set and two r-subsets are adjacent if their intersection is empty. Then we investigate some connection between the minimum size of d-biclique covers of Kneser graphs and cover-free families, where an (r, w; d) cover-free family is a family of subsets of a finite set X such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. The minimum size of a set X for which there exists an (r, w; d) cover-free family with t blocks is denoted by N ((r, w; d), t). We prove that for t > 2r and r > s, we have bc d (KG(t, r)) ≥ bcm(KG(t, s)), where m = N ((r -s, r -s; d), t -2s). Finally, we show that for any 1 ≤ i < r, 1 ≤ j < w, and t ≥ r + w we have N ((r, w; d), t) ≥ N ((r -i, w -j; m), t), where m = N ((i, j; d), t -r -w + i + j).

Introduction

Illegal copy is a major problem in digital data. Frameproof codes are one of many different techniques to prevent products against illegal copy that were first introduced by Boneh and Shaw [START_REF] Boneh | Collusion-secure fingerprinting for digital data[END_REF]. To protect digital data, the distributor marks each copy uniquely with a codeword. These codewords have the property that an illegal copy can trace and back to the buyer. Also, these marks are impossible to remove or change for non-colluding buyers. But, whenever some malicious buyers (that are called pirates) are colluding, they can compare their copies and detect different positions. Colluding buyers have the ability to erase or change detected positions and construct some illegal marks. In order to formulate these conditions we consider the following definitions and notations. Let Γ ⊆ {0, 1} v and |Γ| = t. Γ is called a (v, t)-code and every element of Γ is said to be a codeword. We write w i for the ith component of a word w. Also, the incidence matrix of Γ is a t × v matrix whose rows are the codewords in Γ. Suppose C = {w (u1) , w (u2) , . . . , w (u d ) } ⊆ Γ ⊆ {0, 1} v . For i ∈ {1, 2, . . . , v}, the ith component is said undetectable for the coalition C if

w (u1) i = w (u2) i = • • • = w (u d ) i .
Let U (C) be the set of undetectable components for C. The set

F (C) = {x ∈ {0, 1} v : x| U (C) = w (ui) | U (C)
for all w (ui) ∈ C} represents all possible v-tuples that could be produced by the coalition C by comparing the d codewords.

Definition 1 An r-frameproof code is a subset Γ ⊆ {0, 1} v such that for every C ⊆ Γ where |C| ≤ r, we have F (C) ∩ Γ = C.

Let r -F P C(v, b) denotes an r-frameproof code Γ ⊆ {0, 1} v such that |Γ| = b. The codewords in the set Γare called registered codewords. Therefore, if we have an r-frameproof code, then the pirate in the set C couldn't produce a registered illegal codeword other than their marks; that is not appropriate for the pirate copy. For more details about frameproof codes; see [START_REF] Simon | Frameproof codes[END_REF][START_REF] Boneh | Collusion-secure fingerprinting for digital data[END_REF][START_REF] Stinson | Combinatorial properties and constructions of traceability schemes and frameproof codes[END_REF][START_REF] Tardos | Optimal probabilistic fingerprint codes[END_REF][START_REF] Tardos | Optimal probabilistic fingerprint codes[END_REF]. The following theorem was proved by Stinson,Trung,and Wei [10].

Theorem 1 [10] Suppose Γ is an r -F P C(v, b) with b > 2r -1. Suppose D ⊆ Γ, where |D| = 2r -1.
Then there exists an unregistered word, say maj

(D) ∈ {0, 1} v , such that maj(D) ∈ F (C) for any C ⊆ D with |C| = r.
In view of the aforementioned theorem, maj(D) is a codeword that is produced by the coalition of every r-subset of the set D. Therefore, in an r -F P C, there exist some illegal marks such that it is not possible to identify a pirate user. So they considered another condition and defined secure frameproof codes in which distributor is able to identify at least one pirate of the guilty coalitions.

Definition 2 Suppose that Γ is a (v, t)-code. Γ is said to be an r-secure frameproof code if for any

C 1 , C 2 ⊆ Γ with |C 1 | ≤ r, |C 2 | ≤ r, and C 1 ∩ C 2 = ∅, we have F (C 1 ) ∩ F (C 2 ) = ∅. Also, Γ is termed an r -SFPC(v, t), for short.
In fact, when an illegal mark can be produced by two different r-subsets, in an r -SF P C, there exists at least one user in their intersection; whose can be considered as a pirate user. Stinson and Wei in [START_REF] Stinson | Secure frameproof codes, key distribution patterns, group testing algorithms and related structures[END_REF] studied the relationship between binary secure frameproof codes and combinatorial aspects. In this paper, we establish the relationship between this concept and biclique cover. By a biclique we mean a bipartite graph with vertex set (X, Y ) such that every vertex in X is adjacent to every vertex in Y . Note that every empty graph is a biclique. A d-biclique cover of a graph G of size s is a collection of s bicliques of G such that each edge of G is in at least d of the bicliques. The d-biclique covering number of G, denoted by bc d (G), is defined to be the minimum number of s such that there exists a d-biclique cover of size s for the graph G. For abbreviation, let bc(G) stand for bc 1 (G).

Definition 3 Let X be an n-set and F = {B 1 , . . . , B t } be a family of subsets of X. F is called an (r, w; d)-cover-free family if for any two subsets I, J ⊆ [t] such that |I| = r, |J| = w, and I ∩ J = ∅, the following condition holds

|( i∈I B i ) \ ( j∈J B j )| ≥ d.
We denote it briefly by (r, w; d) -CF F (n, t).

The minimum number of elements of X for which there exists an (r, w; d) -CF F with t members is denoted by N ((r, w; d), t). For convenience, we use the notation N ((r, w), t) instead of N ((r, w; 1), t). This parameter has been studied extensively in the literature; see [START_REF] Vilenkin | Upper bounds on the rate of superimposed (s, l)codes based on engel's inequality[END_REF][START_REF] Hajiabolhassan | Some new bounds on cover-free families through biclique covers[END_REF][START_REF] Sh | On the optimality of trivial (w, r)-cover-free codes[END_REF][START_REF] Stinson | Generalized cover-free families[END_REF]. The incidence matrix of an (r, w; d) -CF F is a t × n binary matrix A such that a ij = 1 whenever j ∈ B i and a ij = 0 otherwise. As usual, we denote by [t] the set {1, 2, . . . , t}, and denote by [t] r the collection of all r-subsets of[t]. The graph I t (r, w) is a bipartite graph with the vertex set ( [t] w , [t] r ) for which a w-subset is adjacent to an r-subset whenever their intersection is empty.

Theorem 2 [START_REF] Hajiabolhassan | Some new bounds on cover-free families through biclique covers[END_REF] For any positive integers r, w, d, and t, where t ≥ r + w, we have

N ((r, w; d), t) = bc d (I t (r, w)).
Throughout this paper, we only consider finite simple graphs. For a graph G, let V (G) and E(G) denote its vertex and edge sets, respectively. The Kneser graph KG(t, r) is the graph with vertex set [t] r , and

A is adjacent to B if A ∩ B = ∅. A homomorphism from G to H is a map φ : V (G) -→ V (H) such that adjacent vertices in G are mapped into adjacent vertices in H, i.e., uv ∈ E(G) implies φ(u)φ(v) ∈ E(H).
In addition, if any edge in H is the image of some edge inG, then φ is termed an onto-edge homomorphism. In this paper, by A c we mean the complement of the set A. In Section 2, we show that for t ≥ 2r, an r-secure frameproof code of size t and length v exists if and only if there exists a 1-biclique cover of size v for the Kneser graph KG(t, r). Also, we wish to investigate some connection between the d-biclique covering number of Kneser graphs and cover-free families. Moreover, we present an upper bound for the biclique covering number of Kneser graphs. In Section 3, we will look more closely at the biclique covering number of Kneser graphs. Also, it is shown that if there exists a Hadamard matrix of order 4d, then N ((1, 1; d), 8d -2) = 4d and bc 2d (K 8d ) = 4d.

Secure Frameproof Codes

For a subset A i of [t], the indicator vector of A i is the vector v Ai = (v 1 , . . . , v t ), where v j = 1 if j ∈ A i and v j = 0 otherwise. Theorem 3 Let r, t, and v be positive integers, where t ≥ 2r. An r -SFPC(v, t) exists if and only if there exists a biclique cover of size v for the Kneser graph KG(t, r).

Proof: Assume that A is the incidence matrix of an r -SFPC(v, t). Assign to the jth column of A, the set A j as follows

A j def = {i| 1 ≤ i ≤ t, a ij = 1}. Now, for 1 ≤ j ≤ v, construct the bicliques G j with vertex set (X j , Y j )
, where the vertices ofX j are all r-subsets of A j and the vertices of

Y j are all r-subsets of A c j , i.e., [t] \ A j . It is easily seen that G j , for 1 ≤ j ≤ v, is a complete bipartite graph of KG(t, r). Let C 1 C 2 be an arbitrary edge of KG(t, r). So C 1 , C 2 ⊆ [t], and C 1 ∩ C 2 = ∅. Since A is the incidence matrix of an r -SFPC(v, t), we have F (C 1 ) ∩ F (C 2 ) = ∅.
This means that there exists a bit position i such that the ith bit of all code words of C 1 is c i , for some c i ∈ {0, 1}, and also the ith bit of all codewords of C 2 is c i + 1 (mod 2). So there exists a column of A such that all entries corresponding to the rows of C 1 are equal to 1 and all entries corresponding to the rows ofC 2 are equal to 0, or vice versa. Hence, C 1 C 2 ∈ E(G i ). Conversely, assume that we have a biclique cover of size v for the graph KG(t, r). Our objective is to construct an r-SFPC. Label graphs in this biclique cover with G 1 , . . . , G v , where G i has as its vertex set (X i , Y i ). Let A i be the union of sets that lie in X i . Consider the indicator vectors of A i 's , for 1 ≤ i ≤ v, and construct the matrix A whose columns are these vectors. Assume that C 1 and C 2 are two disjoint subsets of [t] of size r, i.e., C 1 C 2 ∈ E(KG(t, r)). Let G i be the complete bipartite graph that covers the edge C 1 C 2 . Then in the ith column of the matrix A all entries corresponding to the rows of C 1 are equal to 1 and all entries corresponding to the rows of C 2 are equal to 0, or vice versa. Consequently,

F (C 1 ) ∩ F (C 2 ) = ∅. 2 A covering of a graph G is a subset K of V (G)
such that every edge of G has at least one end in K. The number of vertices in a minimum covering of G is called the covering number of G and denoted byβ(G).

In [START_REF] Stinson | Secure frameproof codes, key distribution patterns, group testing algorithms and related structures[END_REF], Stinson, Trung, and Wei construct anr -SFPC(2 2r-1 r-1 , 2r + 1). Corollary 1 [START_REF] Stinson | Secure frameproof codes, key distribution patterns, group testing algorithms and related structures[END_REF] For any integer r ≥ 0, there exists an r -SFPC(2 2r-1 r-1 , 2r + 1).

Proof: Easily, one can check that the biclique covering number of a graph G without C 4 as a subgraph is equal to the covering number of G. On the other hand, KG(2r + 1, r) does not contain C 4 as a subgraph. So bc(KG(2r + 1, r))) = β(KG(2r + 1, r)). Also, it is a well-known fact that β(KG(t, r)) = t-r r t-1 r-1 . An easy computation confirms the assertion. 2

In the next theorem, we show the relationship between the d-biclique cover of Kneser graphs and coverfree families.

Theorem 4 For any positive integers r, d, and t, where t ≥ 2r, it holds that bc 2d (KG(t, r)) ≤ N ((r, r; d), t) ≤ 2bc d (KG(t, r)).

Proof: First, assume that we have an optimal (r, r; d)-CF F (n, t), i.e., n = N ((r, r; d), t) with incidence matrix A. Assign to the jth column of A, the set A j as follows

A j def = {i| 1 ≤ i ≤ t, a ij = 1}.
Consider the biclique G j with vertex set (X j , Y j ), where the vertices of X j are all r-subsets of A j and the vertices of Y j are all r-subsets of A c j . Also, two vertices are adjacent if the subsets corresponding to these vertices are disjoint. It is not difficult to see that G j 's, for 1 ≤ j ≤ N ((r, r; d), t), form a 2d-biclique cover of KG(t, r). So bc 2d (KG(t, r)) ≤ N ((r, r; d), t). Conversely, assume that we have a d-biclique cover of KG(t, r). Label graphs in this biclique cover with G 1 , . . . , G l , where G i has as its vertex set (X i , Y i ). Let A i be the union of sets that lie in X i and B i be the union of sets that lie in Y i . Obviously, A i and B i are disjoint. Consider the indicator vectors of A i 's and B i 's, for i = 1, . . . , l. Construct the matrix A whose columns are these vectors. Then A is the incidence matrix of an (r, r; d) -CF F (2l, t). So N ((r, r; d), t) ≤ 2bc d (KG(t, r)).

2

Corollary 2 For any positive integers r, and t, where t ≥ 2r, it holds that bc 2 (KG(t, r)) ≤ N ((r, r), t) ≤ 2bc(KG(t, r)).

A similar result has been obtained by Stinson et al. [START_REF] Stinson | Secure frameproof codes, key distribution patterns, group testing algorithms and related structures[END_REF].

Theorem 5 [START_REF] Stinson | Secure frameproof codes, key distribution patterns, group testing algorithms and related structures[END_REF] Let r and t be positive integers, where t ≥ 2r, then 1. If there exists an r -SF P C(v, t), then there exists an (r, r) -CF F (2v, t).

2. Any (r, r)-cover free family is an r-secure frameproof code.

Stinson et al. [START_REF] Stinson | Secure frameproof codes, key distribution patterns, group testing algorithms and related structures[END_REF] have obtained the following upper bounds for SF P C.

Theorem 6 [START_REF] Stinson | Secure frameproof codes, key distribution patterns, group testing algorithms and related structures[END_REF] Suppose that r and t are positive integers and p = 1

-1 2 2r-1 . If v ≥ ln( 1 2 ( t r )( t-r r ))
-ln p , then there exists an r -SF P C(v, t).

The following upper bound is shown in Deng et al. [START_REF] Deng | The Lovász local lemma and its applications to some combinatorial arrays[END_REF], by the Lovász Local Lemma.

Theorem 7 [3]

There exists an r

-SF P C(v, t) if v ≥ ln(e(( t r )( t-r r )-( t-2r r )( t-3r r ))) -ln p
, where

p = 1 -1 2 2r-1 . Let p = 1 -1 2 2r-1 .
Using the approximation e -x ≈ 1 -x, if we set x = 1 2 2r-1 , then we can see that 1 -ln p ≈ 2 2r-1 . In the next theorem, by the alternation method, we present a bound that is a slight improvement of Theorem 6. Also, it is a slight improvement of Theorem 7 provided that t is not large relative to r.

Theorem 8 Let r and t be positive integers. If t > 3r and

v ≥ 2 2r-1 (1 + ln( t 2 r t 2 r )) r-1 i=0 (1 -1 t-2i+1 ),
then there exists an r -SF P C(v, t).

Proof: We show that if v ≥ 2 2r-1 (1 + ln(

t 2 r t 2 r )) r-1 i=0
(1 -1 t-2i+1 ) , then there exists a biclique cover of size v for the Kneser graph KG(t, r). Let A be [t] t 2

. For every member of A, say A i , we can construct the biclique G i with vertex set (X i , Y i ), where the vertices of X i are all r-subsets of A i and the vertices of Y i are all r-subsets of A c i . We define B to be the collection of these bicliques. Let p ∈ [0, 1] be arbitrary, later, we specify an optimized value for p. Let us pick, randomly and independently, each biclique of B with probability p and F be the random set of all bicliques picked and let Y F be the set of all edges AB of the graph KG(t, r) which are not covered by the set F. The expected value of |F| is clearly

t t 2 p. For every edge AB, pr(AB ∈ Y F ) = (1 -p) l where l = 2 t-2r t 2 -r . So the expected value of the |F| + |Y F | is at most t t 2 p + 1 2 t r t-r r (1 -p) 2( t-2r t 2 -r ) .
If we set F = F Y F , then clearly all edges of the graph KG(t, r) are covered by F . So we want to estimate p such that |F | is minimum. For convenient, we bound 1 -p ≤ e -p to obtain

E(|F| + |Y F |) ≤ t t 2 p + 1 2 t r t-r r e -2( t-2r t 2 -r )p .
The right hand side is minimized at p = ln α β , which α = t 2 r t 2 r and β = 2 t-2r t 2 -r where p ∈ [0, 1] if t is sufficiently large respect to r (e.g., t > 3r). So we have an r

-SF P C(v, t) that v ≤ ( t t 2 ) 2( t-2r t 2 -r ) (1 + ln( t 2 r t 2 r )).
Furthermore, it is straightforward to check that

( t t 2 ) 2( t-2r t 2 -r ) ≤ 2 2r-1 r-1 i=0 (1 -1 t-2i+1 ).
Hence, the bound follows. 2

Biclique Cover of Kneser Graphs

By the mentioned results in the previous section, it may be of interest to find some bounds for the biclique covering number of Kneser graphs.

Theorem 9 For any positive integers d, r, s, and t, where t > 2r and r > s, we have

bc d (KG(t, r)) ≥ bc m (KG(t, s)),
where m = N ((r -s, r -s; d), t -2s).

Proof: Let {G 1 , G 2 , . . . , G l } be an optimal d-biclique cover of KG(t, r). Also, assume that G i has as its vertex set (X i , Y i ). Let A i and B i be the union of sets that lie in X i and Y i , respectively. For any 1 ≤ i ≤ l, consider the biclique G i , as a subgraph of KG(t, s), with vertex set (X i , Y i ), where X i is the set of all s-subsets of A i and Y i is the set of all s-subsets of B i . One can check thatG i 's cover all edges of KG(t, s). Moreover, any edge U V ∈ E(KG(t, s)) is contained in at least m-bicliques, where m = N ((r -s, r -s; d), t -2s). To see this, consider the bipartite graph I {U,V } (as an induced subgraph of KG(t, r)) with vertex set (X U , Y V ), where

X U = {W | U ⊆ W ⊆ [t], W ∩ V = ∅, |W | = r} Y V = {W | V ⊆ W ⊆ [t], W ∩ U = ∅, |W | = r}.
It is a simple matter to check that I {U,V } and I t-2s (r -s, r -s) are isomorphic. Also, if G j covers any edge of I {U,V } , then U V is contained in G j . Consequently, by Theorem 2 the assertion follows. 2

In view of the proof of Theorem 9, similarly, one can extend any biclique of I t (r, w) to a biclique of I t (r -i, w -j). Consequently, we have the following theorem.

Theorem 10 Let d, r, w, and t be positive integers, where t ≥ r + w. For any 1 ≤ i < r and 1 ≤ j < w, we have N ((r, w; d), t) ≥ N ((r -i, w -j; m), t), where m = N ((i, j; d), t -r -w + i + j).

The fractional biclique covering number bc * (G) is defined as follows

bc * (G) = inf d bc d (G) d = lim d→∞ bc d (G) d .
It is known that if a graph is edge-transitive, then one can compute its fractional biclique covering number, see [START_REF] Scheinerman | Fractional graph theory[END_REF] for more about fractional graph theory.

Theorem 11 [START_REF] Scheinerman | Fractional graph theory[END_REF] For every non-empty edge-transitive graph G, bc

* (G) = |E(G)| B(G)
, where B(G) is the maximum number of edges among the bicliques of G.

The next result is a consequence of Theorem 10.

Theorem 12 [START_REF] Stinson | Generalized cover-free families[END_REF] Let d, r, w, i, j, and t be non-negative integers, where t ≥ r + w, 1 ≤ i < r, and 1 ≤ j < w. Then N ((r, w; d), t) ≥ N ((i, j; d), t -r -w + i + j) min w-j≤m≤t-r+i t m t-r-w+i+j m-w+j .

Proof: In view of definition of fractional biclique cover and since bc ts (G) ≤ s.bc t (G) for every positive integers t and s, one can conclude that for every graph G, we have t.bc * (G) ≤ bc t (G). By this fact and using Theorem 10, we have

N ((r, w; d), t) ≥ N ((i, j; d), t -r -w + i + j)bc * (I t (r -i, w -j)). (1)
The graph I t (r, w) is an edge-transitive graph. Therefore, using Theorem 11 and an easy calculation bc * (I t (r, w)) = min We know that the image of a biclique under a graph homomorphism is a biclique. This leads us to the following lemma.

Lemma 1 Let G and H be two graphs and φ : G → H be an onto-edge homomorphism. Also, assume that d and t are positive integers and for any edge e ∈ E(H), bc d (φ -1 (e)) ≥ t. Then bc d (G) ≥ bc t (H).

Proof: Let {K 1 , K 2 , . . . , K l } be an optimal d-biclique cover of G. One can check that for any 0 ≤ i ≤ l, φ(K i ) is a biclique and the family {φ(K 1 ), φ(K 2 ), . . . , φ(K l )} is a t-biclique cover of H.

2

Proposition 1 For any positive integers t and r, where t > 2r, we have bc d (KG(t, r)) ≥ bc 3d (KG(t -2, r -1)).

Proof: First, we present an onto-edge homomorphism φ from KG(t, r) to KG(t -2, r -1). To see this, for every vertex A of KG(t, r), define φ(A) := A as follows. If A does not contain both t and t -1, then define A := A \ {maxA}. Otherwise, set A := {x} ∪ A \ {t, t -1}, where x is the maximum element of [t -2] absent from A. It is simple to check that the subgraph induced by the inverse image of any edge of KG(t -2, r -1) contains an induced cycle of size six or an induced matching of size three. Hence, in

view of Lemma 1, if {K 1 , . . . , K l } is a d-biclique cover of KG(t, r), then {φ(K 1 ), . . . , φ(K l )} is a 3d- biclique cover of KG(t -2, r -1). 2
The aforementioned results motivate us to consider the following question.

Question 1 Let d, r, and t be positive integers, where t > 2r. What is the exact value of bc d (KG(t, r))?

Determining the exact value of the parameter N ((r, w; d), t), even for special r, w, d and t, is an interesting and challenging problem that is studied in the literature; see [START_REF] Hajiabolhassan | Some new bounds on cover-free families through biclique covers[END_REF][START_REF] Kim | Some new results on superimposed codes[END_REF][START_REF] Sh | On the optimality of trivial (w, r)-cover-free codes[END_REF][START_REF] Li | Constructions of 2-cover-free families and related separating hash families[END_REF]]. An n × n matrix H with entries +1 and -1 is called a Hadamard matrix of order n whenever HH t = nI. It is not difficult to see that any two columns of H are also orthogonal. If we permute rows or columns or if we multiply some rows or columns by -1, then this property does not change. Two such Hadamard matrices are called equivalent. For a given Hadamard matrix, we can find an equivalent one for which the first row and the first column consist entirely of +1ï¿ 1 2 s. Such a Hadamard matrix is called normalized. We will denote by K - m,m the complete bipartite graph with a perfect matching removed. Obviously, K - m,m is isomorphic to I m (1, 1).

Theorem 13 Let d be a positive integer such that there exists a Hadamard matrix of order 4d, then

1. bc 2d (K 8d ) = 4d, 2. N ((1, 1; d), 8d -2) = bc d (K - 8d-2,8d-2 ) = 4d.
Proof: Let H = [h ij ] be a Hadamard matrix of order 4d. Suppose that K 8d has {u 1 , . . . , u 4d , v 1 , . . . , v 4d } as its vertex set. For the jth column of H, two sets X j and Y j are defined as follows

X j := {u i |h ij = +1} ∪ {v i |h ij = -1} & Y j := {u i |h ij = -1} ∪ {v i |h ij = +1}.
By constructing a bipartite graph G j with vertex set (X j , Y j ), indeed, we assign a biclique to each column. It is well-known that for any two rows of a Hadamard matrix, the number of columns for which corresponding entries in these rows are different in sign, are equal to 2d. So, for i = j the edges u i u j , v i v j , and u i v j of the graph K 8d are covered by 2d bicliques. Also, for the edge u i v i , there exist 4d bicliques that cover it. According to the above argument every edge is covered at least 2d times, so bc 2d (K 8d ) ≤ 4d.

On the other hand, for every graph G, we have

|E(G)| B(G) ≤ bc d (G) d
, where B(G) is the maximum number of edges among the bicliques of G. Therefore, 4d -1 2 ≤ bc 2d (K 8d ). Since bc 2d (K 8d ) is an integer, we have 4d ≤ bc 2d (K 8d ) which completes the proof. For the proof of the second part, assume that H is a normalized Hadamard matrix of order 4d. Delete the first row of H and denote it by H = [h ij ]. Also, assume that K - 8d-2,8d-2 has (X, Y ) as its vertex set where X = {u 1 , . . . , u 4d-1 , v 1 , . . . , v 4d-1 }, Y = {u 1 , . . . , u 4d-1 , v 1 , . . . , v 4d-1 }, and u i u i , v i v i ∈ E(K - 8d-2,8d-2 ). Assign to the jth column of H , two sets X j and Y j as follows

X j := {u i |h ij = +1} ∪ {v i |h ij = -1} & Y j := {u i |h ij = -1} ∪ {v i |h ij = +1}.
By the same argument in the first part of the proof and using the well-known fact that in H every two distinct rows i, j and for any a, b ∈ {-1, +1} there are exactly dcolumns that the corresponding entries are a and b in the rows i and j, respectively, one can see that every edge is covered at least d times. So bc d (K - 8d-2,8d-2 ) ≤ 4d. On the other hand, 4d -2d 4d-1 ≤ bc d (K - 8d-2,8d-2 ), and 2d 4d-1 < 1. Therefore, 4d ≤ bc d (K - 8d-2,8d-2 ) which establishes the second part.

.

  Therefore, according to the inequality 1 it follows that N ((r, w; d), t) ≥ N ((i, j; d), t -r -w + i + j) min

† Email: hhaji@sbu.ac.ir. This research was in part supported by a grant from IPM (No. 90050114). ‡ Email: f.moazami@alzahra.ac.ir.1365-8050 c 2012 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Acknowledgements

This paper has been revised and resubmitted for review while Hossein Hajiabolhassn was on leave at Technical University of Denmark (the academic year 2012-2013). Hossein Hajiabolhassan is grateful to professor Carsten Thomassen for his hospitality and support. Also, the authors wish to thank the anonymous referees for their useful comments.