Word maps and spectra of random graph lifts

We study here the spectra of random lifts of graphs. Let G be a finite connected graph, and let the infinite tree T be its universal cover space. If λ₁ and ρ are the spectral radii of G and T respectively, then, as shown by Friedman (Graphs Duke Math J 118 (2003), 19–35), in almost every n‐lift H of G, all “new” eigenvalues of H are ≤ O(λ ρ^1/2). Here we improve this bound to O(λ ρ^2/3). It is conjectured in (Friedman, Graphs Duke Math J 118 (2003) 19–35) that the statement holds with the bound ρ + o(1) which, if true, is tight by (Greenberg, PhD thesis, 1995). For G a bouquet with d/2 loops, our arguments yield a simple proof that almost every d‐regular graph has second eigenvalue O(d^2/3). For the bouquet, Friedman (2008). has famously proved the (nearly?) optimal bound of . Central to our work is a new analysis of formal words. Let w be a formal word in letters g,…,g. The word map associated with w maps the permutations σ₁,…,σ_k ∈ S_n to the permutation obtained by replacing for each i, every occurrence of g_i in w by σ_i. We investigate the random variable X that counts the fixed points in this permutation when the σ_i are selected uniformly at random. The analysis of the expectation ??(X) suggests a categorization of formal words which considerably extends the dichotomy of primitive vs. imprimitive words. A major ingredient of a our work is a second categorization of formal words with the same property. We establish some results and make a few conjectures about the relation between the two categorizations. These conjectures suggest a possible approach to (a slightly weaker version of) Friedman's conjecture. As an aside, we obtain a new conceptual and relatively simple proof of a theorem of A. Nica (Nica, Random Struct Algorithms 5 (1994), 703–730), which determines, for every fixed w, the limit distribution (as n →∞) of X. A surprising aspect of this theorem is that the answer depends only on the largest integer d so that w = u^d for some word u. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

On smallest triangles

Pick n points independently at random in ?², according to a prescribed probability measure μ, and let Δ ≤ Δ ≤ … be the areas of the () triangles thus formed, in nondecreasing order. If μ is absolutely continuous with respect to Lebesgue measure, then, under weak conditions, the set {n³Δ : i ≥ 1} converges as n → ∞ to a Poisson process with a constant intensity κ(μ). This result, and related conclusions, are proved using standard arguments of Poisson approximation, and may be extended to functionals more general than the area of a triangle. It is proved in addition that if μ is the uniform probability measure on the region S, then κ(μ) ≤ 2/|S|, where |S| denotes the area of S. Equality holds in that κ(μ) = 2/|S| if S is convex, and essentially only then. This work generalizes and extends considerably the conclusions of a recent paper of Jiang, Li, and Vitányi. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 206–223, 2003     

Compactness methods in the theory of homogenization II: Equations in non-divergence form

We prove C^{0, α}, C^{1, α} and C^{1, 1} a priori estimates for solutions of boundary value problems for elliptic operators with periodic coefficients of the form Σ,^j=1a^{i j}(x/?)δ²/δx_iδx_j. The constants in these estimates are independent of the small parameter ?, and hence our results imply strengthened versions of the classical averaging theorems. These results generalize to a wide class of linear operators in non-divergence form, including equations with lower-order terms and nonuniformly oscillating coefficients, as well as to certain nonlinear problems, which we discuss in the last section.     

A generalization of a result of Tran Van Trung on t-designs

We prove that if there exists a t − (v, k, λ) design satisfying the inequality for some positive integer j (where m = min{j, v − k} and n = min {i, t}), then there exists a t − (v + j, k, λ ()) design. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 107–112, 1999     

Phase transitions for random walk asymptotics on free products of groups

Suppose we are given finitely generated groups Γ₁,…,Γ_m equipped with irreducible random walks. Thereby we assume that the expansions of the corresponding Green functions at their radii of convergence contain only logarithmic or algebraic terms as singular terms up to sufficiently large order (except for some degenerate cases). We consider transient random walks on the free product Γ₁* … *Γ_m and give a complete classification of the possible asymptotic behaviour of the corresponding n‐step return probabilities. They either inherit a law of the form ?^nδn log n from one of the free factors Γ_i or obey a ?^nδn^?3/2‐law, where ? < 1 is the corresponding spectral radius and δ is the period of the random walk. In addition, we determine the full range of the asymptotic behaviour in the case of nearest neighbour random walks on free products of the form $\mathbb{Z}^{d_1}\ast \ldots \ast \mathbb{Z}^{d_m}Suppose we are given finitely generated groups Γ₁,…,Γ_m equipped with irreducible random walks. Thereby we assume that the expansions of the corresponding Green functions at their radii of convergence contain only logarithmic or algebraic terms as singular terms up to sufficiently large order (except for some degenerate cases). We consider transient random walks on the free product Γ₁* … *Γ_m and give a complete classification of the possible asymptotic behaviour of the corresponding n‐step return probabilities. They either inherit a law of the form ?^nδn log n from one of the free factors Γ_i or obey a ?^nδn^?3/2‐law, where ? < 1 is the corresponding spectral radius and δ is the period of the random walk. In addition, we determine the full range of the asymptotic behaviour in the case of nearest neighbour random walks on free products of the form $\mathbb{Z}^{d_1}\ast \ldots \ast \mathbb{Z}^{d_m}$. Moreover, we characterize the possible phase transitions of the non‐exponential types n log n in the case Γ₁ * Γ₂. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

A note on bipartite subgraphs of triangle-free graphs

Let G be a triangle-free graph on n points with m edges and vertex degrees d₁, d₂,…, d_n. Let k be the maximum number of edges in a bipartite subgraph of G. In this note we show that k ? m/2 + Σ √d_i. It follows as a corollary that k ? m/2 + cm^3/4.     

An integral-interpolation iterative method for the solution of scalar equations

We study the use of integral information on a functionf in the iterative process for the solution of a nonlinear scalar equationf(x)=0.It is shown that for the information onf given by:

On the minimum size of tight hypergraphs

A k-graph, H = (V, E), is tight if for every surjective mapping f: V → {1,….k} there exists an edge α ? E sicj tjat f|_α is injective. Clearly, 2-graphs are tight if and only if they are connected. Bounds for the minimum number ? of edges in a tight k-graph with n vertices are given. We conjecture that ? for every n and prove the equality when 2n + 1 is prime. From the examples, minimal embeddings of complete graphs into surfaces follow. © 1992 John Wiley & Sons, Inc.     

Comonotone approximation of twice differentiable periodic functions

In the case where a 2π-periodic function f is twice continuously differentiable on the real axis ℝ and changes its monotonicity at different fixed points y _i ∈ [− π, π), i = 1,…, 2s, s ∈ ℕ (i.e., on ℝ, there exists a set Y := {y _i } _i∈ℤ of points y _i = y _i+2s + 2π such that the function f does not decrease on [y _i , y _i−1] if i is odd and does not increase if i is even), for any natural k and n, n ≥ N(Y, k) = const, we construct a trigonometric polynomial T _n of order ≤n that changes its monotonicity at the same points y _i ∈ Y as f and is such that

On series of signed vectors and their rearrangements

Let x₁,…,x_m∈ \input amssym $ \Bbb R$ n be a sequence of vectors with ∥x_i∥₂ ≤ 1 for all i. It is proved that there are signs ε₁,…,ε_m = ±1 such that where C₁, C₂ are some numerical constants. It is also proved that there are signs ε,…,ε = ±1 and a permutation π of {1,…,m} such that where C^′ is some other numerical constant. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Tangential Convergence of Temperatures and Harmonic Functions in Besov and in Triebel-Lizorkin Spaces

We study the maximal function Mf(x) = sup |f(x + y, t)| when Ω is a region in the (y,t) Ω upper half space R and f(x, t) is the harmonic extension to R₊^N+1 of a distribution in the Besov space B^α_p,q(R^N) or in the Triebel-Lizorkin space F^α_p,q(R^N). In particular, we prove that when Ω= {|_y|^{N/ (N-αp)} < t < 1} the operator M is bounded from F (R^N) into L^p (R^N). The admissible regions for the spaces B (R^N) with p < q are more complicated.     

Finding blocks and other patterns in a random coloring of ℤ

Let ξ = (ξ_k)_k∈? be i.i.d. with P(ξ_k = 0) = P(ξ_k = 1) = 1/2, and let S: = (S_k) be a symmetric random walk with holding on ?, independent of ξ. We consider the scenery ξ observed along the random walk path S, namely, the process (χ_k := ξ). With high probability, we reconstruct the color and the length of blockⁿ, a block in ξ of length ≥ n close to the origin, given only the observations (χ_k). We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on blockⁿ and in the interval [?3ⁿ,3ⁿ]. Moreover, we reconstruct with high probability a piece of ξ of length of the order 3 around blockⁿ, given only 3 observations collected by the random walker starting on the boundary of blockⁿ. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Jointly ergodic measure-preserving transformations

The notion of ergodicity of a measure-preserving transformation is generalized to finite sets of transformations. The main result is that ifT ₁,T ₂, …,T _s are invertible commuting measure-preserving transformations of a probability space (X, ?, μ) then 1 $$\frac{1}{{N - M}}\sum\limits_{n = M}^{N - 1} {T{}_1^n } f_1 .T_2^n f_2 .....T_s^n f_s \xrightarrow[{N - M \to \propto }]{{I^2 (X)}}(\int_X {f1d\mu )} (\int_X {f2d\mu )...(\int_X {fsd\mu )} } $$ for anyf ₁,f ₂, …,f _s∈L ^x (X, ?, μ) iffT ₁×T ₂×…×T _s and all the transformationsT _iT_j ¹,i≠j, are ergodic. The multiple recurrence theorem for a weakly mixing transformation follows as a special case.     

On Σ1-definable Functions Provably Total in I ∏

We prove the following theorem: Let φ(x) be a formula in the language of the theory PA^? of discretely ordered commutative rings with unit of the form ?yφ′(x,y) with φ′ and let ∈ Δ₀ and let fφ: ? → ? such that f_φ(x) = y iff φ′(x,y) & (?z < y) φ′(x,z). If I ∏ ∈(?x ≥ 0), φ then there exists a natural number K such that I ∏ ? ?y?x(x > y ? ?φ(x) < x^K). Here I ∏₁^? denotes the theory PA^? plus the scheme of induction for formulas φ(x) of the form ?yφ′(x,y) (with φ′) with φ′ ∈ Δ₀.     

A less formal approach to kaluza-klein formalism

The action integrals (a) and , corresponding respectively to gravitational and gravitational-electromagnetic phenomena, are shown to be related under continuous groups of null translations. This relation motivates a modified Kaluza—Klein formalism for which the classical cylindrical metric preserving transformations (c)y ⁵ = =x ⁵ +f ⁵(x ^j ),y ⁱ =f ⁱ (x ^j ) fori = 1, 2, 3, 4 are replaced by (d)y ⁵ =x ⁵,y ⁱ =f ⁱ (x ^j ,x ⁵). The cylindrical metric of V⁵ is nevertheless preserved under (d), since it is assumed thatV ⁵ admits a metric of the form (corresponding to (a)) and that (d) defines a continuous group of null translations in theV ⁴ metric defined byg _ij whenx ⁵ is considered the group parameter. Application of (d) leads to the cylindrical metric corresponding to (b). The resulting electromagnetic fieldsF _ij =B _i,j –B _j,i are then related to the curvatures of theV ⁴ corresponding tog _ij andh _ij ; in particular it is shown that and . When it is shown thatF _ij is a null electromagnetic field which is generally non-trivial. Some physical and geometric interpretations of the mathematical results are also presented.Dedicated to Professor A. Ostrowski on the occasion of his 75th birthday     

An Erdös-Ko-Rado theorem for the subcubes of a cube

LetP be that partially ordered set whose elements are vectors x=(x ₁, ...,x _n ) withx _i ε {0, ...,k} (i=1, ...,n) and in which the order is given byx≦y iffx _i =y _i orx _i =0 for alli. LetN _i (P)={x εP : |{j:x _j ≠ 0}|=i}. A subsetF ofP is called an Erdös-Ko-Rado family, if for allx, y εF it holdsx ≮y, x ≯ y, and there exists az εN ₁(P) such thatz≦x andz≦y. Let ? be the set of all vectorsf=(f ₀, ...,f _n ) for which there is an Erdös-Ko-Rado familyF inP such that |N _i (P) ∩F|=f _i (i=0, ...,n) and let 〈?〉 be its convex closure in the (n+1)-dimensional Euclidean space. It is proved that fork≧2 (0, ..., 0) and \(\left( {0,...,0,\overbrace {i - component}^{\left( {\begin{array}{*{20}c} {n - 1} \\ {i - 1} \\ \end{array} } \right)}k^{i - 1} ,0,...,0} \right)\) (i=1, ...,n) are the vertices of 〈?〉.     

The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A_n=min_π ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA_n→ζ(2)=π²/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001     

On the density of 2‐colorable 3‐graphs in which any four points span at most two edges

Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)$. We improve the previously best known lower and upper bounds of 0.25682 and 3/10?ε, respectively, by showing that This implies the following new upper bound for the Turán density of K In order to establish these results we use a combination of the properties of computer‐generated extremal 3‐graphs for small n and an argument based on “super‐saturation”. Our computer results determine the exact values of ex(n, K) for n≤19 and ex₂(n, K) for n≤17, as well as the sets of extremal 3‐graphs for those n. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105–114, 2010     

Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

We consider a canonical Ramsey type problem. An edge‐coloring of a graph is called m‐good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a properly edge‐colored copy of G, and let g(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = K_t, we have c₁mt²/ln t ≤ f(m, K_t) ≤ c₂mt², and cmt³/ln t ≤ g(m, K_t) ≤ cmt³/ln t, where c₁, c₂, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Are the degrees of the best (co)convex and unconstrained polynomial approximations the same? II

In Part I of the paper, we have proved that, for every α > 0 and a continuous function f, which is either convex (s = 0) or changes convexity at a finite collection Y _s = {y _i } ^s _i=1 of points y _i ∈ (-1, 1),