Introduced in 1963, Glauber dynamics is one of the most practiced and extensively studied methods for sampling the Ising model on lattices. It is well known that at high temperatures, the time it takes this chain to mix in L1 on a system of size n is O(log n). Whether in this regime there is cutoff, i.e. a sharp transition in the L1-convergence to equilibrium, is a fundamental open problem: If so, as conjectured by Peres, it would imply that mixing occurs abruptly at (c+o(1)) log n for some fixed c > 0, thus providing a rigorous stopping rule for this MCMC sampler. However, obtaining the precise asymptotics of the mixing and proving cutoff can be extremely challenging even for fairly simple Markov chains. Already for the one-dimensional Ising model, showing cutoff is a longstanding open problem.
We settle the above by establishing cutoff and its location at the high temperature regime of the Ising model on the lattice with periodic boundary conditions. Our results hold for any dimension and at any temperature where there is strong spatial mixing: For Z2 this carries all the way to the critical temperature. Specifically, for fixed d ³ 1, the continuous-time Glauber dynamics for the Ising model on (Z/nZ)^d with periodic boundary conditions has cutoff at (d/2l¥)log n, where l¥ is the spectral gap of the dynamics on the infinite-volume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even understanding its stationary distribution is limited.
The proof hinges on a new technique for translating L1-mixing to L2-mixing of projections of the chain, which enables the application of logarithmic-Sobolev inequalities. The technique is general and carries to other monotone and anti-monotone spin-systems, e.g. gas hard-core, Potts, anti-ferromagentic Ising, arbitrary boundary conditions, etc.
Let C1 be the largest component of the Erdős-Rényi random graph $G(n,p)$. The mixing time of random walk on C1 in the strictly supercritical regime, $p=c/n$ with fixed $c>1$, was shown to have order $\log^2 n$ by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, $p=(1+\epsilon)/n$ where $\lambda=\epsilon^3 n$ is bounded, Nachmias and Peres proved that the mixing time on C1 is of order $n$. However, it was unclear how to interpolate between these results, and estimate the mixing time as the giant component emerges from the critical window. Indeed, even the asymptotics of the diameter of C1 in this regime were only recently obtained by Riordan and Wormald, as well as the present authors and Kim.
In this paper we show that for $p=(1+\epsilon)/n$ with $\lambda=\epsilon^3 n\to\infty$ and $\lambda=o(n)$, the mixing time on C1 is with high probability of order $(n/\lambda)\log^2 \lambda$. In addition, we show that this is the order of the largest mixing time over all components, both in the slightly supercritical and in the slightly subcritical regime (i.e., $p=(1-\epsilon)/n$ with $\lambda$ as above).
In their seminal paper from 1983, Erdős and Szemerédi showed that any $n$ distinct integers induce either $n^{1+\epsilon}$ distinct sums of pairs or that many distinct products, and conjectured a lower bound of $n^{2-o(1)}$. They further proposed a generalization of this problem, in which the sums and products are taken along the edges of a given graph $G$ on $n$ labeled vertices. They conjectured a version of the sum-product theorem for general graphs that have at least $n^{1+\epsilon}$ edges.
In this work, we consider sum-product theorems for sparse graphs, and show that this problem has important consequences already when $G$ is a matching (i.e., $n/2$ disjoint edges): Any lower bound of the form $n^{1/2+\delta}$ for its sum-product over the integers implies a lower bound of $n^{1+\delta}$ for the original Erdős-Szemerédi problem.
In contrast, over the reals the minimal sum-product for the matching is $\Theta(\sqrt{n})$, hence this approach has the potential of achieving lower bounds specialized to the integers. We proceed to give lower and upper bounds for this problem in different settings. In addition, we provide tight bounds for sums along expanders.
A key element in our proofs is a reduction from the sum-product of a matching to the maximum number of translates of a set of integers into the perfect squares. This problem was originally studied by Euler, and we obtain a stronger form of Euler's result using elliptic curve analysis.
We study the diameter of C1, the largest component of the Erdős-Rényi random graph $G(n,p)$ emerging from the critical window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$. This parameter was extensively studied for fixed $\epsilon > 0$, yet results for $\epsilon=o(1)$ outside the critical window were only obtained very recently: Riordan and Wormald gave precise estimates on the diameter, however these do not cover the entire supercritical regime (namely, when $\epsilon^3 n\to\infty$ arbitrarily slowly); {\L}uczak and Seierstad estimated its order throughout this regime, yet their upper and lower bounds differ by a factor of $1000/7$.
We show that for any $\epsilon=o(1)$ with $\epsilon^3n\to\infty$, the diameter of $C_$ is with high probability asymptotic to $D(\epsilon,n)=(3/\epsilon)\log(\epsilon^3 n)$. We also prove that, in this regime, the diameter of the 2-core of $C_$ is w.h.p. asymptotic to $(2/3) D(\epsilon,n)$, and the maximal distance in it between any pair of kernel vertices is w.h.p. asymptotic to $(5/9) D(\epsilon,n)$.
The proofs rely on a recent structure result for the supercritical giant component, which reduces the problem of estimating distances between its vertices to the study of passage times in first-passage percolation.
We provide a complete description of the giant component of the Erdős-Rényi random graph $G(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$.
Our description is particularly simple for $\epsilon = o(n^{-1/4})$, where the giant component C1 is contiguous with the following model (i.e., every graph property that holds with high probability for this model also holds w.h.p. for C1). Let $Z$ be normal with mean $(2/3) \epsilon^3 n$ and variance $\epsilon^3 n$, and let $K$ be a random $3$-regular graph on $2\lfloor Z\rfloor$ vertices. Replace each edge of $K$ by a path, where the path lengths are i.i.d.\ geometric with mean $1/\epsilon$. Finally, attach an independent Poisson($1-\epsilon$)-Galton-Watson tree to each vertex.
A similar picture is obtained for larger $\epsilon=o(1)$, in which case the random 3-regular graph is replaced by a random graph with $N_k$ vertices of degree $k$ for $k\geq 3$, where $N_k$ has mean and variance of order $\epsilon^k n$.
This description enables us to determine fundamental characteristics of the supercritical random graph. Namely, we can infer the asymptotics of the diameter of the giant component for any rate of decay of $\epsilon$, as well as the mixing time of the random walk on C1.
In the classical balls-and-bins paradigm, where n balls are placed independently and uniformly in n bins, typically the number of bins with at least two balls in them is Q(n) and the maximum number of balls in a bin is Q(log n)/(log log n)). It is well known that when each round offers k independent uniform options for bins, it is possible to typically achieve a constant maximal load if and only if k= W(log n). Moreover, it is possible w.h.p. to avoid any collisions between n/2 balls if k > log2 n.
In this work, we extend this into the setting where only m bits of memory are available. We establish a tradeoff between the number of choices k and the memory m, dictated by the quantity km/n. Roughly put, we show that for k m » n one can achieve a constant maximal load, while for k m « n no substantial improvement can be gained over the case k=1 (i.e., a random allocation).
For any k = W(log n) and m=W(log2 n), one can achieve a constant load w.h.p. if k m = W(n), yet the load is unbounded if km=o(n). Similarly, if k m > C n then n/2 balls can be allocated without any collisions w.h.p., whereas for k m < e n there are typically W(n) collisions. Furthermore, we show that the load is w.h.p. at least log(n/m)/[log k + log log(n/m)]. In particular, for k=polylog(n), if m = n1-d then the optimal maximal load is Q((log n)/(log log n)) (the same as in the case k=1), while m=2n suffices to ensure a constant load. Finally, we analyze non-adaptive allocation algorithms and give tight upper and lower bounds for their performance.
In the heat-bath Glauber dynamics for the Ising model on the lattice, physicists believe that the spectral gap of the continuous-time chain exhibits the following behavior. For some critical inverse-temperature fixed bc, the inverse-gap is bounded for b < bc, polynomial in the surface area for b = bc and exponential in it for b > bc. This has been proved for Z2 except at criticality. So far, the only underlying geometry where the critical behavior has been confirmed is the complete graph. Recently, the dynamics for the Ising model on a regular tree, also known as the Bethe lattice, has been intensively studied. The facts that the inverse-gap is bounded for b < bc and exponential for b > bc were established, where bc is the critical spin-glass parameter, and the tree-height h plays the role of the surface area.
In this work, we complete the picture for the inverse-gap of the Ising model on the b-ary tree, by showing that it is indeed polynomial in h at criticality. The degree of our polynomial bound does not depend on b, and furthermore, this result holds under any boundary condition. We also obtain analogous bounds for the mixing-time of the chain. In addition, we study the near critical behavior, and show that for b > bc, the inverse-gap and mixing-time are both exp[Q((b-bc) h)].
The cutoff phenomenon describes a sharp transition in the convergence of a family of ergodic finite Markov chains to equilibrium. Many natural families of chains are believed to exhibit cutoff, and yet establishing this fact is often extremely challenging. An important such family of chains is the random walk on G(n,d), a random d-regular graph on n vertices. It is well known that the spectral gap of this class of chains for d ³ 3 fixed is constant, implying a mixing-time of O(log n). According to a conjecture of Peres, the simple random walk on G(n,d) for such d should then exhibit cutoff w.h.p. As a special case of this, Durrett conjectured that the mixing time of the lazy random walk on a random 3-regular graph is w.h.p. (6+o(1))log2 n.
In this work we confirm the above conjectures, and establish cutoff in total-variation, its location and its optimal window, both for simple and for non-backtracking random walks on G(n,d). Namely, for any fixed d ³ 3, the simple random walk on G(n,d) w.h.p. has cutoff at d/(d-2)logd-1 n with window order (log n)1/2. Surprisingly, the non-backtracking random walk on G(n,d) w.h.p. has cutoff already at logd-1 n with constant window order. We further extend these results to G(n,d) for any d=no(1) (beyond which the mixing time is O(1)), provide efficient algorithms for testing cutoff, as well as give explicit constructions where cutoff occurs.
We study Glauber dynamics for the Ising model on the complete graph on n vertices, known as the Curie-Weiss Model. It is well known that at high temperature (b < 1) the mixing time is Q(n log n), whereas at low temperature (b > 1) it is exp(Q(n)). Recently, Levin, Luczak and Peres considered a censored version of this dynamics, which is restricted to non-negative magnetization. They proved that for fixed b > 1, the mixing-time of this model is Q(n log n), analogous to the high-temperature regime of the original dynamics. Furthermore, they showed cutoff for the original dynamics for fixed b < 1. The question whether the censored dynamics also exhibits cutoff remained unsettled.
In a companion paper, we extended the results of Levin et al. into a complete characterization of the mixing-time for the Currie-Weiss model. Namely, we found a scaling window of order 1/Ön around the critical temperature bc=1, beyond which there is cutoff at high temperature. However, determining the behavior of the censored dynamics outside this critical window seemed significantly more challenging.
In this work we answer the above question in the affirmative, and establish the cutoff point and its window for the censored dynamics beyond the critical window, thus completing its analogy to the original dynamics at high temperature. Namely, if b = 1 + d for some d > 0 such that d2 n ® ¥, then the mixing-time has order (n/d) log(d2 n). The cutoff constant is (1/2+[2(z2 b/d - 1)]-1), where z is the unique positive root of g(x)=tanh(b x)-x, and the cutoff window has order n/d.
We consider Glauber dynamics for the Ising model on the complete graph on n vertices, known as the Curie-Weiss model. It is well-known that the mixing-time in the high temperature regime (b < 1) is of order n log n , whereas the mixing-time in the case b > 1 is exponential in n . Recently, Levin, Luczak and Peres proved that for any fixed b < 1 there is cutoff at time [2(1-b)]-1 n log n with a window of order n , whereas the mixing-time at the critical temperature b=1 is Q(n3/2). It is natural to ask how the mixing-time transitions from Q( n log n) to Q( n3/2) and finally to exp(Q(n)). That is, how does the mixing-time behave when b=b(n) is allowed to tend to 1 as n ® ¥ .
In this work, we obtain a complete characterization of the mixing-time of the dynamics as a function of the temperature, as it approaches its critical point bc=1. In particular, we find a scaling window of order 1/Ön around the critical temperature. In the high temperature regime, bc=1-d for some 0 < d < 1 so that d2n ® ¥ with n , the mixing-time has order (n / d) log(d2n), and exhibits cutoff with constant 1/2 and window size n / d. In the critical window, bc=1±d where d2n is O(1), there is no cutoff, and the mixing-time has order n3/2. At low temperature, bc=1+d for d < 0 with d2n ® ¥ and d=o(1), there is no cutoff, and the mixing time has order (n / d) exp((3/4+o(1))d2n) .
A sender holds a word x consisting of n blocks xi , each of t bits, and wishes to broadcast a codeword to m receivers, R1,...,Rm . Each receiver Ri is interested in one block, and has prior side information consisting of some subset of the other blocks. Let bt be the minimum number of bits that has to be transmitted when each block is of length t , and let b be the limit b=limt®¥bt / t . In words, b is the average communication cost per bit in each block (for long blocks). Finding the coding rate b , for such an informed broadcast setting, generalizes several coding theoretic parameters related to Informed Source Coding on Demand, Index Coding and Network Coding.
In this work we show that usage of large data blocks may strictly improve upon the trivial encoding which treats each bit in the block independently. To this end, we provide general bounds on bt , and prove that for any constant C there is an explicit broadcast setting in which b=2 but b1 > C. One of these examples answers a question of Lubetzky and Stav.
In addition, we provide examples with the following counterintuitive direct-sum phenomena. Consider a union of several mutually independent broadcast settings. The optimal code for the combined setting may yield a significant saving in communication over concatenating optimal encodings for the individual settings. This result also provides new non-linear coding schemes which improve upon the largest known gap between linear and non-linear Network Coding, thus improving the results of Dougherty, Freiling, and Zeger.
The proofs are based on a relation between this problem and results in the study of Witsenhausen's rate, OR graph products, colorings of Cayley graphs, and the chromatic numbers of Kneser graphs.
In this paper we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on n labeled vertices. At each round we are presented with K=K(n) edges, chosen uniformly at random from the missing ones, and are asked to add one of them to the current graph. The goal is to create a Hamilton cycle as soon as possible.
We show that this problem has three regimes, depending on the value of K. For K=o(log n), the threshold for Hamiltonicity is (1+o(1))n/(2K) log n, i.e., typically we can construct a Hamilton cycle K times faster that in the usual random graph process. When K=w(log n) we can essentially waste almost no edges, and create a Hamilton cycle within n+o(n) rounds with high probability. Finally, in the intermediate regime where K has order log n, the threshold has order n and we obtain upper and lower bounds that differ by a multiplicative factor of 3.
The cutoff phenomenon describes a case where a Markov chain exhibits a sharp transition in its convergence to stationarity. In 1996, Diaconis surveyed this phenomenon, and asked how one could recognize its occurrence in families of finite ergodic Markov chains. In 2004, the third author noted that a necessary condition for cutoff in a family of reversible chains is that the product of the mixing-time and spectral-gap tends to infinity, and conjectured that in many settings, this condition should also be sufficient. Diaconis and Saloff-Coste (2006) verified this conjecture for continuous-time birth-and-death chains, started at an endpoint, with convergence measured in separation. It is natural to ask whether the conjecture holds for these chains in the more widely used total-variation distance.
In this work, we confirm the above conjecture for all continuous-time or lazy discrete-time birth-and-death chains, with convergence measured via total-variation distance. Namely, if the product of the mixing-time and spectral-gap tends to infinity, the chains exhibit cutoff at the maximal hitting time of the stationary distribution median, with a window of at most the geometric mean between the relaxation-time and mixing-time.
In addition, we show that for any lazy (or continuous-time) birth-and-death chain with stationary distribution p, the separation 1 - pt(x,y)/p(y) is maximized when x,y are the endpoints. Together with the above results, this implies that total-variation cutoff is equivalent to separation cutoff in any family of such chains.
The following source coding problem was introduced by Birk and Kol: a sender holds a word x Î {0,1}n, and wishes to broadcast a codeword to n receivers, R1,...,Rn . The receiver Ri is interested in xi , and has prior side information comprising some subset of the n bits. This corresponds to a directed graph G on n vertices, where i j is an edge iff Ri knows the bit xj . An index code for G is an encoding scheme which enables each Ri to always reconstruct xi, given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram and Kol (FOCS 2006). They introduced a graph parameter, minrk2(G), which completely characterizes the length of an optimal linear index code for G. The authors of BBJK showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact always optimal.
In this work, we disprove the main conjecture of BBJK in the following strong sense: for any e > 0 and sufficiently large n, there is an n-vertex graph G so that every linear index code for G requires codewords of length at least n1-e, and yet a non-linear index code for G has a word length of ne. This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson.
Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. Alon, Benjamini, Lubetzky and Sodin studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length n on a high-girth n-vertex regular expander, is typically (1+o(1))log n / log log n, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes.
In this work, we answer the above question by combining a generalized form of Brun's sieve with some extensions of the ideas in Alon et al. Let Nt denote the number of vertices visited precisely t times by a non-backtracking random walk of length n on a regular n-vertex expander of fixed degree and girth g. We prove that if g=w(1), then for any fixed t, Nt / n is typically 1/(et!)+o(1). Furthermore, if g=W(log log n), then Nt / n is typically (1+o(1))/(et!) uniformly on all t £ (1-o(1))log n / log log n and 0 for all t ³ (1+o(1))log n / log log n. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables.
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as fast as the mixing rate of the simple random walk. The closer the expander is to a Ramanujan graph, the higher the ratio between the above two mixing rates is.
As an application, we show that if G is a high-girth regular expander on n vertices, then a typical non-backtracking random walk of length n on G does not visit a vertex more than (1+o(1))log n / log log n times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing n balls to n bins uniformly, in contrast to the simple random walk on G, which almost surely visits some vertex W(log n) times.
Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be l-cross-intersecting iff |AÇB| = l for all A Î A and B Î B. Denote by Pl(n) the maximum value of |A||B| over all such pairs. The best known upper bound on Pl(n) is Q(2n), by Frankl and Rödl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ³ 2l, a simple construction of an l-cross-intersecting pair (A,B) with |A||B| = {2l choose l}2n-2l=Q(2n/Öl), and conjectured that this is best possible. Consequently, Sgall asked whether or not Pl(n) decreases with l.
In this paper, we confirm the above conjecture of Ahlswede et al. for any sufficiently large l, implying a positive answer to the above question of Sgall as well. By analyzing the linear spaces of the characteristic vectors of A,B over R, we show that there exists some l0 > 0, such that Pl(n) £ {2l choose l}2n-2l for all l ³ l0. Furthermore, we determine the precise structure of all the pairs of families which attain this maximum.
In [Amir et al.], the authors consider the generalization $\Gor$ of the Erdős-Rényi random graph process $G$, where instead of adding new edges uniformly, $\Gor$ gives a weight of size 1 to missing edges between pairs of isolated vertices, and a weight of size $K\in[0,\infty)$ otherwise. This can correspond to the linking of settlements or the spreading of an epidemic. The authors investigate $\tgor(K)$, the critical time for the appearance of a giant component as a function of $K$, and prove that $\tgor=(1+o(1))\frac{4}{\sqrt{3K}}$, using a proper timescale.
In this work, we show that a natural variation of the model $\Gor$ has interesting properties. Define the process $\Gand$, where a weight of size $K$ is assigned to edges between pairs of non-isolated vertices, and a weight of size 1 otherwise. We prove that the asymptotical behavior of the giant component threshold is essentially the same for $\Gand$, and namely $\tgand / \tgor$ tends to $\frac{64\sqrt{6}}{\pi(24+\pi^2)}\approx 1.47$ as $K\to\infty$. However, the corresponding thresholds for connectivity satisfy $\tcand / \tcor=\max\{{1/2},K\}$ for every $K>0$. Following the methods of [Amir et al.], $\tgand$ is characterized as the singularity point to a system of differential equations, and computer simulations of both models agree with the analytical results as well as with the asymptotic analysis. In the process, we answer the following question: when does a giant component emerge in a graph process where edges are chosen uniformly out of all edges incident to isolated vertices, while such exist, and otherwise uniformly? This corresponds to the value of $\tgand(0)$, which we show to be ${3/2}+\frac{4}{3\mathrm{e}^2-1}$.
The k-th p-power of a graph G is the graph on the vertex set V(G)k, where two k-tuples are adjacent iff the number of their coordinates which are adjacent in G is not congruent to 0 modulo p. The clique number of powers of G is poly-logarithmic in the number of vertices, thus graphs with small independence numbers in their p-powers do not contain large homogenous subsets. We provide algebraic upper bounds for the asymptotic behavior of independence numbers of such powers, settling a conjecture of Alon and Lubetzky up to a factor of 2. For precise bounds on some graphs, we apply Delsarte's linear programming bound and Hoffman's eigenvalue bound. Finally, we show that for any nontrivial graph G, one can point out specific induced subgraphs of large p-powers of G with neither a large clique nor a large independent set. We prove that the larger the Shannon capacity of `G is, the larger these subgraphs are, and if G is the complete graph, then some p-power of G matches the bounds of the Frankl-Wilson Ramsey construction, and is in fact a subgraph of a variant of that construction.
We present a readily applicable way to go beyond the accuracy limits of current optical flow estimators. Modern optical flow algorithms employ the coarse to fine approach. We suggest to upgrade this class of algorithms, by adding over-fine interpolated levels to the pyramid. Theoretical analysis of the coarse to over-fine approach explains its advantages in handling flow-field discontinuities and simulations show its benefit for sub-pixel motion. By applying the suggested technique to various multiscale optical flow algorithms, we reduced the estimation error by 10%-30% on the common test sequences. Using the coarse to over-fine technique, we obtain optical flow estimation results that are currently the best for benchmark sequences.
The tensor product of two graphs, $G$ and $H$, has a vertex set $V(G)\times V(H)$ and an edge between $(u,v)$ and $(u',v')$ iff both $u u' \in E(G)$ and $v v' \in E(H)$. Let $A(G)$ denote the limit of the independence ratios of tensor powers of $G$, $\lim \alpha(G^n)/|V(G^n)|$. This parameter was introduced by Brown, Nowakowski and Rall, who showed that $A(G)$ is lower bounded by the vertex expansion ratio of independent sets of $G$. In this note we study the relation between these parameters further, and ask whether they are in fact equal. We present several families of graphs where equality holds, and discuss the effect the above question has on various open problems related to tensor graph products.
The $k$-th power of a graph $G$ is the graph whose vertex set is $V(G)^k$, where two distinct $k$-tuples are adjacent iff they are equal or adjacent in $G$ in each coordinate. The Shannon capacity of $G$, $c(G)$, is $\lim_{k\to\infty}\alpha(G^k)^{1/k}$, where $\alpha(G)$ denotes the independence number of $G$. When $G$ is the characteristic graph of a channel $\mathcal{C}$, $c(G)$ measures the effective alphabet size of $\mathcal{C}$ in a zero-error protocol. A sum of channels, $\mathcal{C}=\sum_i \mathcal{C}_i$, describes a setting when there are $t\geq 2$ senders, each with his own channel $\mathcal{C}_i$, and each letter in a word can be selected from either of the channels. This corresponds to a disjoint union of the characteristic graphs, $G=\sum_i G_i$.
We show that for any fixed $t$ and any family $F$ of subsets of $T={1,2,...,t}$, there are $t$ graphs $G_1,G_2, ...,G_t$, so that for every subset $I$ of $T$, the Shannon capacity of the disjoint union $\sum_{i \in I} G_i$ is "large" if $I$ contains a member of $F$, and is "small" otherwise.
A random graph process, $\Gorg[1](n)$, is a sequence of graphs on $n$ vertices which begins with the edgeless graph, and where at each step a single edge is added according to a uniform distribution on the missing edges. It is well known that in such a process a giant component (of linear size) typically emerges after $(1+o(1))\frac{n}{2}$ edges (a phenomenon known as ``the double jump''), i.e., at time $t=1$ when using a timescale of $n/2$ edges in each step.
We consider a generalization of this process, $\Gorg[K](n)$, which gives a weight of size 1 to missing edges between pairs of isolated vertices, and a weight of size $K \in [0,\infty)$ otherwise. This corresponds to a case where links are added between $n$ initially isolated settlements, where the probability of a new link in each step is biased according to whether or not its two endpoint settlements are still isolated. Combining methods of \cite{SpencerWormald} with analytical techniques, we describe the typical emerging time of a giant component in this process, $t_c(K)$, as the singularity point of a solution to a set of differential equations. We proceed to analyze these differential equations and obtain properties of $\Gorg$, and in particular, we show that $t_c(K)$ strictly decreases from 3/2 to 0 as $K$ increases from 0 to $\infty$, and that $t_c(K) = \frac{4}{\sqrt{3K}}(1 + o(1))$. Numerical approximations of the differential equations agree both with computer simulations of the process $\Gorg(n)$ and with the analytical results.
The isoperimetric constant of a graph $G$ on $n$ vertices, $i(G)$, is the minimum of $\frac{|\partial S|}{|S|}$, taken over all nonempty subsets $S\subset V(G)$ of size at most $n/2$, where $\partial S$ denotes the set of edges with precisely one end in $S$. A random graph process on $n$ vertices, $\widetilde{G}(t)$, is a sequence of $\binom{n}{2}$ graphs, where $\widetilde{G}(0)$ is the edgeless graph on $n$ vertices, and $\widetilde{G}(t)$ is the result of adding an edge to $\widetilde{G}(t-1)$, uniformly distributed over all the missing edges. We show that in almost every graph process $i(\widetilde{G}(t))$ equals the minimal degree of $\widetilde{G}(t)$ as long as the minimal degree is $o(\log n)$. Furthermore, we show that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically $\Theta(\log n)$, the ratio between the isoperimetric constant and the minimum degree falls from 1 to 1/2, its final value.
What is the maximum possible number, f3(n) , of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g3(n) , of vectors in {0,1,2}n such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a graph G . Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of G (normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity, while the other grows linearly. As a special case, it follows that f3(n) = Q(2n) whereas g3(n) = Q(n).
The independence numbers of powers of graphs have been long studied, under several definitions of graph products, and in particular, under the strong graph product. We show that the series of independence numbers in strong powers of a fixed graph can exhibit a complex structure, implying that the Shannon Capacity of a graph cannot be approximated (up to a sub-polynomial factor of the number of vertices) by any arbitrarily large, yet fixed, prefix of the series. This is true even if this prefix shows a significant increase of the independence number at a given power, after which it stabilizes for a while.
Delivering popular web pages to the clients results in high bandwidth and high load on the web servers. A method to overcome this problem is to send these pages, requested by many users, via multicast. In this paper, we provide an analytic criterion to determine which pages to multicast, and analyze the overall saving factor as compared with a unicast delivery. The analysis is based on the well known observation that page popularity follows a Zipf-like distribution. Interestingly, we can obtain closed-form analytical expressions for the saving factor, that show the multicast advantage as a function of the site hit-rate, the allowed latency and the Zipf parameter.