Abstract. Let [Formula: see text] be the book graph which consists of [Formula: see text] copies of triangles all sharing a common edge. Let [Formula: see text] be a cycle of length [Formula: see text]. In 1978, Rousseau and Sheehan initiated the study of the book–cycle Ramsey number. A lot of effort has been made to determine the value of [Formula: see text] since then. In [ Ars Combin., 31 (1991), pp. 239–248], Faudree, Rousseau, and Sheehan mentioned the following: “we know practically nothing about [Formula: see text] when [Formula: see text] is even and greater than four. Also, the problem of computing [Formula: see text] when [Formula: see text] is odd and [Formula: see text] and [Formula: see text] are nearly equal provides an unanswered test of strength.” Answering the second part of the question above, the second and fifth authors recently obtained the value of [Formula: see text] for [Formula: see text] and [Formula: see text] being large. However, the value of [Formula: see text] is previously unknown for [Formula: see text] and [Formula: see text] being even as well as [Formula: see text] and [Formula: see text] being odd. In this paper, for even [Formula: see text], we manage to determine the value of [Formula: see text] provided that [Formula: see text] is linear with [Formula: see text] and [Formula: see text] is large enough. Thus this makes progress towards the first part of the question above. In addition, for odd [Formula: see text], we are able to obtain the value of [Formula: see text] for [Formula: see text] and [Formula: see text] being large.

We study structural properties of preferential attachment graphs (with parameter m ≥ 1 giving the number of attachment choices that each new vertex makes) which intervene in two complementary algorithmic/statistical/information-theoretic problems involving the information shared between a random graph's labels and its structure: in structural compression, we seek to compactly describe a graph's structure by a bit string, throwing away its label information; in node arrival order recovery, we seek to recover node labels, given only a graph structure. In particular, we study the typical size of the automorphism group, as well as some shape parameters (such as the number of linear extensions and height) of the directed version of the graph, which in turn allows us to estimate the typical number of admissible labeled representatives of a given graph structure. Our result on the automorphism group positively settles a conjecture to the effect that, provided that m ≥ 3, preferential attachment graphs are asymmetric with high probability, and completes the characterization of the number of symmetries for a broad range of parameters of the model (i.e., for all fixed m). These results allow us to give an algorithmically efficient, asymptotically optimal algorithm for compression of unlabeled preferential attachment graphs. To show the optimality of our scheme, we also derive new, precise estimates of the Shannon entropy of both the unlabeled and labeled version of the model. Our results also imply inapproximability results for the problem of node arrival order recovery.

Let $P^k_\ell$ denote the loose $k$-path of length $\ell$ and let $f^k_\ell(n,m)$ be the minimum value of $\Delta(H)$ over all $P^k_\ell$-free $k$-graphs $H$ with $n$ vertices and $m$ edges. In this paper we study the behavior of $f^4_2(n,m)$ and $f^3_3(n,m)$ and characterize the structure of extremal hypergraphs. In particular, it is shown that when $m\sim n^2/8$ the value of each of these functions drops down from $\Theta(n^2)$ to $\Theta(n)$.

We investigate a problem of maintaining a target population of mobile agents in a distributed system. The purpose of the agents is to perform certain activities, so the goal is to avoid overpopulation (leading to waste of resources) as well as underpopulation (resulting in a poor service). We assume that there must be no centralized control over the number of agents, since it might result in system's vulnerability. We analyze a simple protocol in which each node keeps at most one copy of an agent and if there is a single agent in a node, a new agent is born with a certain probability p. At each time step the agents migrate independently at random to chosen locations. We show that during a protocol execution the number of agents stabilizes around a level depending on p. We derive analytically simple formulas that determine probability p based on the target fraction of nodes holding an agent. The previous proposals of this type were based on experimental data only.

Let ${\mathcal R}(n,k)$ denote the random k‐ary relation defined on the set $[n]=\{1,2,\dots,n\}$. We show that the probability that $([n], {\mathcal R}(n,k))$ is projective tends to one, as either n or k tends to infinity. This result implies that for most relational systems $(B,{{\underline{R}}})$ the ${{\textrm{CSP}}}(B,{{\underline{R}}})$ problem is NP‐complete (and thus that the dichotomy conjecture holds with probability 1), and confirms a conjecture of Rosenberg [I. G. Rosenberg, Rocky Mountain J. Math., 3 (1973), pp. 631–639].

The behavior of a greedy algorithm which estimates the height of a random, labelled rooted tree is studied. A self-similarity argument is used to characterize the limit distribution of the length H of the path found by such an algorithm in a random rooted tree as the unique solution of an integral equation. Furthermore, it is shown that $$\lim_{n\rightarrow\infty}\frac{{\rm{E}} H}{\sqrt n} =\frac{\sqrt{2\pi}}{2\sqrt 2-{\rm{ln}} (3+2\sqrt 2)} = 2.352139...,$$ i.e., the expected length of the path constructed by the algorithm is roughly 93.8 of the expected height of a random rooted tree.

A practical suboptimal (variable source coding) algorithm for lossy data compression is presented. This scheme is based on approximate string matching, and it naturally extends the lossless Lempel-Ziv (1977) data compression scheme. Among others we consider the typical length of an approximately repeated pattern within the first n positions of a stationary mixing sequence where D percent of mismatches is allowed. We prove that there exists a constant r/sub 0/(D) such that the length of such an approximately repeated pattern converges in probability to 1/r/sub 0/(D) log n (pr.) but it almost surely oscillates between 1/r/sub -/spl infin//(D) log n and 2/r/sub 1/(D) log n, where r/sub -/spl infin//(D)>r/sub 0/(D)>r/sub 1/(D)/2 are some constants. These constants are natural generalizations of Renyi entropies to the lossy environment. More importantly, we show that the compression ratio of a lossy data compression scheme based on such an approximate pattern matching is asymptotically equal to r/sub 0/(D). We also establish the asymptotic behavior of the so-called approximate waiting time N/sub l/ which is defined as the time until a pattern of length C repeats approximately for the first time. We prove that log N/sub l//l/spl rarr/r/sub 0/(D) (pr.) as l/spl rarr//spl infin/. In general, r/sub 0/(D)>R(D) where R(D) is the rate distortion function. Thus for stationary mixing sequences we settle in the negative the problem investigated by Steinberg and Gutman by showing that a lossy extension of the Wyner-Ziv (1989) scheme cannot be optimal.

For a tree T a perfect T-matching in a graph G is a subgraph of G with at least $|G| - |T| + 1$ vertices, each component of which is isomorphic to T. Two properties, $\mathcal{A}$ and $\mathcal{B}$, are introduced where the former is a modification of the fact that the largest component of G has a perfect T-matching and the latter is a suitably chosen necessary condition for $\mathcal{A}$ expressed in terms of forbidden “pendant” subgraphs. We show that in the random graph process $\hat G_n $ the hitting times of both above properties coincide. This paper is the first one that deals with the hitting times of nonmonotone graph properties. It extends results of Bollobás and Frieze [Ann. Discrete Math., 28 (1985), pp. 23–46] and Bollobás and Thomason [Ann. Discrete Math., 28 (1985), pp. 47–98].