Poisson approximation for non-backtracking random walks

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. The authors of [3] 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 [3]. Let N _t 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 = ω(1), then for any fixed t, N _t /n is typically 1/et! + o(1). Furthermore, if g = Ω(log log n), then N _t /n is typically 1+o(1)/et! niformly 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.     

Uniformly cross intersecting families

Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be ℓ-cross-intersecting iff |A∩B|=ℓ for all A∈ A and B∈B. Denote by P _e (n) the maximum value of |A||B| over all such pairs. The best known upper bound on P _e (n) is Θ(2 ⁿ ), by Frankl and R?dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2ℓ, a simple construction of an ℓ-cross-intersecting pair (A,B) with |A||B| = $ \left( {{*{20}c} {2\ell } \\ \ell \\ } \right) $ \left( {\begin{array}{*{20}c} {2\ell } \\ \ell \\ \end{array} } \right) 2 ^n−2ℓ = Θ(2 ⁿ /$ \sqrt \ell $ \sqrt \ell ), and conjectured that this is best possible. Consequently, Sgall asked whether or not P _e (n) decreases with ℓ.     

The distance between superspecial abelian varieties with real multiplication

Let L be a totally real field of strict class number one and let OL be its ring of integers. Let p be a rational prime which is unramified in L. We consider the distance between two superspecial abelian varieties with real multiplication in characteristic p, where by “distance” we mean the minimal degree of an OL-isogeny. We give upper and lower bounds on the distance between superspecial abelian varieties with real multiplication by L in characteristic p in terms of p and the degree and discriminant of L.     

Sums and products along sparse graphs

In their seminal paper from 1983, Erdős and Szemerédi showed that any n distinct integers induce either n ^1+ɛ 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+ɛ edges.     

Extension of Arrow's theorem to symmetric sets of tournaments

Arrow's impossibility theorem [K.J. Arrow, Social Choice and Individual Values, Wiley, New York, NY, 1951] shows that the set of acyclic tournaments is not closed to non-dictatorial Boolean aggregation. In this paper we extend the notion of aggregation to general tournaments and we show that for tournaments with four vertices or more any proper symmetric (closed to vertex permutations) subset cannot be closed to non-dictatorial monotone aggregation and to non-neutral aggregation. We also demonstrate a proper subset of tournaments that is closed to parity aggregation for an arbitrarily large number of vertices. This proves a conjecture of Kalai [Social choice without rationality, Reviewed NAJ Economics 3(4)] for the non-neutral and the non-dictatorial and monotone cases and gives a counter example for the general case.     

On the maximum number of edges in quasi-planar graphs

A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] proved that these graphs have a linear number of edges. We give a simple proof for this fact that yields the better upper bound of 8n edges for n vertices. Our best construction with 7n−O(1) edges comes very close to this bound. Moreover, we show matching upper and lower bounds for several relaxations and restrictions of this problem. In particular, we show that the maximum number of edges of a simple quasi-planar topological graph (i.e., every pair of edges have at most one point in common) is 6.5n−O(1), thereby exhibiting that non-simple quasi-planar graphs may have many more edges than simple ones.     

In-plane and out-of-plane ferroelectric instabilities in epitaxial SrTiO3 films

The in-plane and out-of-plane ferroelectric instabilities in compressed (100)-epitaxial SrTiO3 films were examined by infrared reflection spectroscopy. The strongly stiffened in-plane soft mode frequency softened very slowly on cooling. On the other hand, the silent mode appeared at around 150 K, indicating an out-of-plane ferroelectric transition. This behavior points to a split of in-plane and out-of-plane ferroelectric instability temperatures due to the lowered symmetry of the SrTiO3 lattice caused by mechanical misfit strain. Infrared spectroscopy provides a possibility to detect such an effect in the strained epitaxial ferroelectric films.     

Harmonic Pinnacles in the Discrete Gaussian Model

The 2D Discrete Gaussian model gives each height function \({\eta : {\mathbb{Z}^2\to\mathbb{Z}}}\) a probability proportional to \({\exp(-\beta \mathcal{H}(\eta))}\), where \({\beta}\) is the inverse-temperature and \({\mathcal{H}(\eta) = \sum_{x\sim y}(\eta_x-\eta_y)^2}\) sums over nearest-neighbor bonds. We consider the model at large fixed \({\beta}\), where it is flat unlike its continuous analog (the Discrete Gaussian Free Field). We first establish that the maximum height in an \({L\times L}\) box with 0 boundary conditions concentrates on two integers M, M + 1 with \({M\sim \sqrt{(1/2\pi\beta)\log L\log\log L}}\). The key is a large deviation estimate for the height at the origin in \({\mathbb{Z}^{2}}\), dominated by “harmonic pinnacles”, integer approximations of a harmonic variational problem. Second, in this model conditioned on \({\eta\geq 0}\) (a floor), the average height rises, and in fact the height of almost all sites concentrates on levels H, H + 1 where \({H\sim M/\sqrt{2}}\). This in particular pins down the asymptotics, and corrects the order, in results of Bricmont et al. (J. Stat. Phys. 42(5–6):743–798, 1986), where it was argued that the maximum and the height of the surface above a floor are both of order \({\sqrt{\log L}}\). Finally, our methods extend to other classical surface models (e.g., restricted SOS), featuring connections to p-harmonic analysis and alternating sign matrices.     

Neutron multiplicities in inelastic collisions of132Xe with197Au

The multiplicities of neutrons emitted from the light and heavy fragments, respectively, in the inelastic scattering of 7.5 MeV/amu¹³² Xe ions from¹⁹⁷Au have been studied as a function of total energy loss. The measured multiplicity ratios are close to the Au-Xe mass ratio for all Q-values, consistent with a rapid thermalization of the excitation energy. The absolute multiplicity values are lower than expected and suggest significant pre-equilibrium effects.     

Acetic Acid Based Sol-Gel PLZT Thin Films: Processing and Characterization

PLZT 4/65/35 thin films were prepared by the acetic acid based sol-gel route. The choice of lanthanum precursor, i.e., acetate or nitrate, influences the functional group content of formamide modified sols and the microstructure of the thin films. The lanthanum nitrate based PLZT thin film deposited on Si/SiO2/TiO2 /Pt/TiO2 substrate has a columnar perovskite grain structure, while the lanthanum acetate based one is characterized by a lead-silicon containing reaction layer beneath the platinum electrode. Although lead is depleted from the PLZT thin film the perovskite structure is retained by the use of the top layer with a large excess of PbO.