On the internal path length of d‐dimensional quad trees

It is proved that the internal path length of a d‐dimensional quad tree after normalization converges in distribution. The limiting distribution is characterized as a fixed point of a random affine operator. We obtain convergence of all moments and of the Laplace transforms. The moments of the limiting distribution can be evaluated from the recursion and lead to first order asymptotics for the moments of the internal path lengths. The analysis is based on the contraction method. In the final part of the paper we state similar results for general split tree models if the expectation of the path length has a similar expansion as in the case of quad trees. This applies in particular to the m‐ary search trees. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 5: 25–41, 1999     

d‐homogeneous and d‐ultrahomogeneous linear spaces

A linear space S is d‐homogeneous if, whenever the linear structures induced on two subsets S₁ and S₂ of cardinality at most d are isomorphic, there is at least one automorphism of S mapping S₁ onto S₂. S is called d‐ultrahomogeneous if each isomorphism between the linear structures induced on two subsets of cardinality at most d can be extended into an automorphism of S. We have proved in [11;] (without any finiteness assumption) that every 6‐homogeneous linear space is homogeneous (that is d‐homogeneous for every positive integer d). Here we classify completely the finite nontrivial linear spaces that are d‐homogeneous for d ≥ 4 or d‐ultrahomogeneous for d ≥ 3. We also prove an existence theorem for infinite nontrivial 4‐ultrahomogeneous linear spaces. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 321–329, 2000     

Unique weak solutions of the d‐dimensional micropolar equation with fractional dissipation

This article examines the existence and uniqueness of weak solutions to the d‐dimensional micropolar equations (d=2 or d=3) with general fractional dissipation (?Δ)^αu and (?Δ)^βw. The micropolar equations with standard Laplacian dissipation model fluids with microstructure. The generalization to include fractional dissipation allows simultaneous study of a family of equations and is relevant in some physical circumstances. We establish that, when $\alpha \ge \frac{1}{2}$ and $\beta \ge \frac{1}{2}$, any initial data (u₀,w₀) in the critical Besov space $u_0\in B_{2,1}^{1+\frac{d}{2}?2\alpha }({?}^d)$ and $w_0\in B_{2,1}^{1+\frac{d}{2}?2\beta }({?}^d)$ yields a unique weak solution. For α ≥ 1 and β=0, any initial data $u_0\in B_{2,1}^{1+\frac{d}{2}?2\alpha }({?}^d)$ and $w_0\in B_{2,1}^{\frac{d}{2}}({?}^d)$ also leads to a unique weak solution as well. The regularity indices in these Besov spaces appear to be optimal and can not be lowered in order to achieve the uniqueness. Especially, the 2D micropolar equations with the standard Laplacian dissipation, namely, α=β=1, have a unique weak solution for $(u_0,w_0)\in B_{2,1}^0$. The proof involves the construction of successive approximation sequences and extensive a priori estimates in Besov space settings.     

A Gallai–Edmonds‐type structure theorem for path‐matchings

As a generalization of matchings, Cunningham and Geelen introduced the notion of path‐matchings. We give a structure theorem for path‐matchings which generalizes the fundamental Gallai–Edmonds structure theorem for matchings. Our proof is purely combinatorial. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 93–102, 2004     

On semi‐classical d‐orthogonal polynomials

In this paper a general theory of semi‐classical d‐orthogonal polynomials is developed. We define the semi‐classical linear functionals by means of a distributional equation , where Φ and Ψ are matrix polynomials. Several characterizations for these semi‐classical functionals are given in terms of the corresponding d‐orthogonal polynomials sequence. They involve a quasi‐orthogonality property for their derivatives and some finite‐type relations.     

Disjoint perfect matchings in 3‐uniform hypergraphs

For a hypergraph H, let denote the minimum vertex degree in H. Kühn, Osthus, and Treglown proved that, for any sufficiently large integer n with , if H is a 3‐uniform hypergraph with order n and then H has a perfect matching, and this bound on is best possible. In this article, we show that under the same conditions, H contains at least pairwise disjoint perfect matchings, and this bound is sharp.     

One‐dimensional q‐Dirac equation

In this paper, we introduce a q‐analog of 1‐dimensional Dirac equation. We investigate the existence and uniqueness of the solution of this equation. Later, we discuss some spectral properties of the problem, such as formally self‐adjointness, the case that the eigenvalues are real, orthogonality of eigenfunctions, Green function, existence of a countable sequence of eigenvalues, and eigenfunctions forming an orthonormal basis of . Finally, we give some examples.     

Four‐dimensional contact ‐submanifolds in

The analogue of ‐submanifolds in (almost) Kählerian manifolds is the concept of contact ‐submanifolds in Sasakian manifolds. These are submanifolds for which the structure vector field ξ is tangent to the submanifold and for which the tangent bundle of M can be decomposed as , where is invariant with respect to the endomorphism φ and is antiinvariant with respect to φ. The lowest possible dimension for M in which this decomposition is non trivial is the dimension 4. In this paper we obtain a complete classification of four‐dimensional contact ‐submanifolds in and for which the second fundamental form restricted to and vanishes identically.     

Mixed two‐grid finite difference methods for solving one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations

The aim of this paper is to propose mixed two‐grid finite difference methods to obtain the numerical solution of the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. The finite difference equations at all interior grid points form a large‐sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a family of finite difference methods for discretizing the spatial and time derivatives. The obtained system has been solved by two‐grid method, where the two‐grid method is used for solving the large‐sparse linear systems. Also, in the proposed method, the spectral radius with local Fourier analysis is calculated for different values of h and Δt. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. Copyright © 2016 John Wiley & Sons, Ltd.     

Asymptotic expansions for the voltage potentials with two‐dimensional and three‐dimensional thin interfaces

We derive asymptotic formulae for two‐dimensional and three‐dimensional steady state voltage potentials associated with thin conductivity imperfections having no uniform thickness. These formulae recover highly conducting inclusions and those with interfacial resistance. Our calculations are rigorous and based on layer potential techniques. Copyright © 2011 John Wiley & Sons, Ltd.     

Two‐dimensional adaptive Fourier decomposition

One‐dimensional adaptive Fourier decomposition, abbreviated as 1‐D AFD, or AFD, is an adaptive representation of a physically realizable signal into a linear combination of parameterized Szegö and higher‐order Szegö kernels of the context. In the present paper, we study multi‐dimensional AFDs based on multivariate complex Hardy spaces theory. We proceed with two approaches of which one uses Product‐TM Systems; and the other uses Product‐Szegö Dictionaries. With the Product‐TM Systems approach, we prove that at each selection of a pair of parameters, the maximal energy may be attained, and, accordingly, we prove the convergence. With the Product‐Szegö dictionary approach, we show that pure greedy algorithm is applicable. We next introduce a new type of greedy algorithm, called Pre‐orthogonal Greedy Algorithm (P‐OGA). We prove its convergence and convergence rate estimation, allowing a weak‐type version of P‐OGA as well. The convergence rate estimation of the proposed P‐OGA evidences its advantage over orthogonal greedy algorithm (OGA). In the last part, we analyze P‐OGA in depth and introduce the concept P‐OGA‐Induced Complete Dictionary, abbreviated as Complete Dictionary. We show that with the Complete Dictionary P‐OGA is applicable to the Hardy H² space on 2‐torus. Copyright © 2016 John Wiley & Sons, Ltd.     

Meyniel's conjecture holds for random d‐regular graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In a separate paper, we showed that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. The result was obtained by showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. In this paper, this deterministic result is used to show that the conjecture holds asymptotically almost surely for random d‐regular graphs when d = d(n) ≥ 3.     

The micromechanics of three‐dimensional collagen‐I gels

We study the micromechanics of collagen‐I gel with the goal of bridging the gap between theory and experiment in the study of biopolymer networks. Three‐dimensional images of fluorescently labeled collagen are obtained by confocal microscopy, and the network geometry is extracted using a 3D network skeletonization algorithm. Each fiber is modeled as an elastic beam that resists stretching and bending, and each crosslink is modeled as torsional spring. The stress–strain curves of networks at three different densities are compared with rheology measurements. The model shows good agreement with experiment, confirming that strain stiffening of collagen can be explained entirely by geometric realignment of the network, as opposed to entropic stiffening of individual fibers. The model also suggests that at small strains, crosslink deformation is the main contributer to network stiffness, whereas at large strains, fiber stretching dominates. As this modeling effort uses networks with realistic geometries, this analysis can ultimately serve as a tool for understanding how the mechanics of fibers and crosslinks at the microscopic level produce the macroscopic properties of the network. © 2010 Wiley Periodicals, Inc. Complexity 16: 22‐28, 2011     

Strong convergence of two‐dimensional Vilenkin‐Fourier series

We prove that certain means of the quadratical partial sums of the two‐dimensional Vilenkin‐Fourier series are uniformly bounded operators from the Hardy space to the space for We also prove that the sequence in the denominator cannot be improved.     

Anomalous scaling for three‐dimensional Cahn‐Hilliard fronts

We prove the stability of the one‐dimensional kink solution of the Cahn‐Hilliard equation under d‐dimensional perturbations for d ≥ 3. We also establish a novel scaling behavior of the large‐time asymptotics of the solution. The leading asymptotics of the solution is characterized by a length scale proportional to t^1/3 instead of the usual t^1/2 scaling typical to parabolic problems. © 2004 Wiley Periodicals, Inc.     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.     

Automorphisms of higher‐dimensional Hadamard matrices

This article derives from first principles a definition of equivalence for higher‐dimensional Hadamard matrices and thereby a definition of the automorphism group for higher‐dimensional Hadamard matrices. Our procedure is quite general and could be applied to other kinds of designs for which there are no established definitions for equivalence or automorphism. Given a two‐dimensional Hadamard matrix H of order ν, there is a Product Construction which gives an order ν proper n‐dimensional Hadamard matrix P⁽ⁿ⁾(H). We apply our ideas to the matrices P⁽ⁿ⁾(H). We prove that there is a constant c > 1 such that any Hadamard matrix H of order ν > 2 gives rise via the Product Construction to cν inequivalent proper three‐dimensional Hadamard matrices of order ν. This corrects an erroneous assertion made in the literature that ”P⁽ⁿ⁾(H) is equivalent to “P⁽ⁿ⁾(H′) whenever H is equivalent to H′.” We also show how the automorphism group of P⁽ⁿ⁾(H) depends on the structure of the automorphism group of H. As an application of the above ideas, we determine the automorphism group of P⁽ⁿ⁾(Hk) when Hk is a Sylvester Hadamard matrix of order 2^k. For ν = 4, we exhibit three distinct families of inequivalent Product Construction matrices P⁽ⁿ⁾(H) where H is equivalent to H₂. These matrices each have large but non‐isomorphic automorphism groups. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 507–544, 2008     

Universality in two‐dimensional enhancement percolation

We consider a type of dependent percolation introduced in 2 , where it is shown that certain “enhancements” of independent (Bernoulli) percolation, called essential, make the percolation critical probability strictly smaller. In this study we first prove that, for two‐dimensional enhancements with a natural monotonicity property, being essential is also a necessary condition to shift the critical point. We then show that (some) critical exponents and the scaling limit of crossing probabilities of a two‐dimensional percolation process are unchanged if the process is subjected to a monotonic enhancement that is not essential. This proves a form of universality for all dependent percolation models obtained via a monotonic enhancement (of Bernoulli percolation) that does not shift the critical point. For the case of site percolation on the triangular lattice, we also prove a stronger form of universality by showing that the full scaling limit 12 , 13 is not affected by any monotonic enhancement that does not shift the critical point. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The acyclic edge chromatic number of a random d‐regular graph is d + 1

We prove the theorem from the title: the acyclic edge chromatic number of a random d‐regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge chromatic number of any graph G. It also represents an analog of a result of Robinson and the second author on edge chromatic number. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 69–74, 2005     

Three‐dimensional quadratic nonconforming brick element

A new nonconforming brick element with quadratic convergence for the energy norm is introduced. The nonconforming element consists of on a cube [?1,1]³, and 14 degree of freedom (DOF). Two types of DOF are introduced. One consists of the value at the eight vertices and six face‐centroids and the other consists of the value at the eight vertices and the integration value of six faces. Error estimates of optimal order are derived in both broken energy and norms for second‐order elliptic problems. If a genuine hexahedron, which is not a parallelepiped, is included in the partition, the proposed element is also convergent, but with a lower order. Copyright © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 158–174, 2014