More complete intersection theorems

The seminal complete intersection theorem of Ahlswede and Khachatrian gives the maximum cardinality of a $k$-uniform $t$-intersecting family on $n$ points, and describes all optimal families. In recent work, we extended this theorem to the weighted setting, giving the maximum ${\mu }_p$ measure of a $t$-intersecting family on $n$ points. In this work, we prove two new complete intersection theorems. The first gives the supremum ${\mu }_p$ measure of a $t$-intersecting family on infinitely many points, and the second gives the maximum cardinality of a subset of ${\mathbb{Z}}_m^n$ in which any two elements $x,y$ have $t$ positions $i_1,\dots ,i_t$ such that $x_{i_j}?y_{i_j}\in \{?(s?1),\dots ,s?1\}$. In both cases, we determine the extremal families, whenever possible.     

Monotonicity of uniqueness for percolation on Cayley graphs: all infinite clusters are born simultaneously

. Consider site or bond percolation with retention parameter p on an infinite Cayley graph. In response to questions raised by Grimmett and Newman (1990) and Benjamini and Schramm (1996), we show that the property of having (almost surely) a unique infinite open cluster is increasing in p. Moreover, in the standard coupling of the percolation models for all parameters, a.s. for all p ₂>p ₁>p _c , each infinite p ₂-cluster contains an infinite p ₁-cluster; this yields an extension of Alexander's (1995) “simultaneous uniqueness” theorem. As a corollary, we obtain that the probability θ _v (p) that a given vertex v belongs to an infinite cluster is depends continuously on p throughout the supercritical phase p>p _c . All our results extend to quasi-transitive infinite graphs with a unimodular automorphism group. Received: 22 December 1997 / Revised version: 1 July 1998     

Competing first passage percolation on random regular graphs

We consider two competing first passage percolation processes started from uniformly chosen subsets of a random regular graph on N vertices. The processes are allowed to spread with different rates, start from vertex subsets of different sizes or at different times. We obtain tight results regarding the sizes of the vertex sets occupied by each process, showing that in the generic situation one process will occupy vertices, for some . The value of α is calculated in terms of the relative rates of the processes, as well as the sizes of the initial vertex sets and the possible time advantage of one process. The motivation for this work comes from the study of viral marketing on social networks. The described processes can be viewed as two competing products spreading through a social network (random regular graph). Considering the processes which grow at different rates (corresponding to different attraction levels of the two products) or starting at different times (the first to market advantage) allows to model aspects of real competition. The results obtained can be interpreted as one of the two products taking the lion share of the market. We compare these results to the same process run on d dimensional grids where we show that in the generic situation the two products will have a linear fraction of the market each. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 534–583, 2017     

Surface‐plasmon wavefront and spectral shaping by near‐field holography

Surface‐plasmon‐polariton waves are two‐dimensional electromagnetic surface waves that propagate at the interface between a metal and a dielectric. These waves exhibit unusual and attractive properties, such as high spatial confinement and enhancement of the optical field, and are widely used in a variety of applications, such as sensing and subwavelength optics. The ability to precisely control the spatial and spectral properties of the surface‐plasmon wave is required in order to support the growing interest in both research and applications of plasmonic waves, and to bring it to the next level. Here, we review the challenges and methods for shaping the wavefront and spectrum of plasmonic waves. In particular, we present the recent advances in plasmonic spatial and spectral shaping, which are based on the realization of plasmonic holograms for the optical nearfield.

     

Can Extra Updates Delay Mixing?

We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance or the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a Hamming metric, single-site dynamics mixes in O(n log n) steps on an n-vertex graph. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of log n compared to updates at uniform random locations on an n-vertex graph. Our result is especially effective in comparing block and single-site dynamics; it has already been used in works of Martinelli, Toninelli, Sinclair, Mossel, Sly, Ding, Lubetzky, and Peres in various combinations.     

Large deviations for random walks on Galton–Watson trees: averaging and uncertainty

 In the study of large deviations for random walks in random environment, a key distinction has emerged between quenched asymptotics, conditional on the environment, and annealed asymptotics, obtained from averaging over environments. In this paper we consider a simple random walk {X _n } on a Galton–Watson tree T, i.e., on the family tree arising from a supercritical branching process. Denote by |X _n | the distance between the node X _n and the root of T. Our main result is the almost sure equality of the large deviation rate function for |X _n |/n under the “quenched measure” (conditional upon T), and the rate function for the same ratio under the “annealed measure” (averaging on T according to the Galton–Watson distribution). This equality hinges on a concentration of measure phenomenon for the momentum of the walk. (The momentum at level n, for a specific tree T, is the average, over random walk paths, of the forward drift at the hitting point of that level). This concentration, or certainty, is a consequence of the uncertainty in the location of the hitting point. We also obtain similar results when {X _n } is a λ-biased walk on a Galton–Watson tree, even though in that case there is no known formula for the asymptotic speed. Our arguments rely at several points on a “ubiquity” lemma for Galton–Watson trees, due to Grimmett and Kesten (1984). Received: 15 November 2000 / Revised version: 27 February 2001 / Published online: 19 December 2001     

Secret-Sharing Schemes for Very Dense Graphs

A secret-sharing scheme realizes a graph if every two vertices connected by an edge can reconstruct the secret while every independent set in the graph does not get any information on the secret. Similar to secret-sharing schemes for general access structures, there are gaps between the known lower bounds and upper bounds on the share size for graphs. Motivated by the question of what makes a graph “hard” for secret-sharing schemes (that is, they require large shares), we study very dense graphs, that is, graphs whose complement contains few edges. We show that if a graph with \(n\) vertices contains \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }\) edges for some constant \(0 \le \beta <1\), then there is a scheme realizing the graph with total share size of \(\tilde{O}(n^{5/4+3\beta /4})\). This should be compared to \(O(n^2/\log (n))\), the best upper bound known for the total share size in general graphs. Thus, if a graph is “hard,” then the graph and its complement should have many edges. We generalize these results to nearly complete \(k\)-homogeneous access structures for a constant \(k\). To complement our results, we prove lower bounds on the total share size for secret-sharing schemes realizing very dense graphs, e.g., for linear secret-sharing schemes, we prove a lower bound of \(\Omega (n^{1+\beta /2})\) for a graph with \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }\) edges.