Finite fields and the 1‐chromatic number of orientable surfaces

The 1‐chromatic number χ₁(S_p) of the orientable surface S_p of genus p is the maximum chromatic number of all graphs which can be drawn on the surface so that each edge is crossed by no more than one other edge. We show that if there exists a finite field of order 4m+1, m≥3, then 8m+2≤χ₁(S)≤8m+3, where 8m+3 is Ringel's upper bound on χ₁(S). © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 179–184, 2010     

Law of large numbers for increasing subsequences of random permutations

Let the random variable Z_n,k denote the number of increasing subsequences of length k in a random permutation from S_n, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Robust characterizations of k‐wise independence over product spaces and related testing results

A discrete distribution D over Σ₁ ×··· ×Σ_n is called (non‐uniform) k ‐wise independent if for any subset of k indices {i₁,…,i_k} and for any z₁∈Σ,…,z_k∈Σ, Pr_X～D[X···X = z₁···z_k] = Pr_X～D[X = z₁]···Pr_X～D[X = z_k]. We study the problem of testing (non‐uniform) k ‐wise independent distributions over product spaces. For the uniform case we show an upper bound on the distance between a distribution D from k ‐wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. Such a bound was previously known only when the underlying domain is {0,1}ⁿ. For the non‐uniform case, we give a new characterization of distributions being k ‐wise independent and further show that such a characterization is robust based on our results for the uniform case. These results greatly generalize those of Alon et al. (STOC'07, pp. 496–505) on uniform k ‐wise independence over the Boolean cubes to non‐uniform k ‐wise independence over product spaces. Our results yield natural testing algorithms for k ‐wise independence with time and sample complexity sublinear in terms of the support size of the distribution when k is a constant. The main technical tools employed include discrete Fourier transform and the theory of linear systems of congruences.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

How many normal measures can ℵ carry?

Relative to the existence of a supercompact cardinal with a measurable cardinal above it, we show that it is consistent for ?₁ to be regular and for ? to be measurable and to carry precisely τ normal measures, where τ ≥ ? is any regular cardinal. This extends the work of [2], in which the analogous result was obtained for ?_{ω +1} using the same hypotheses (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Total relative displacement of vertex permutations of K

Let α denote a permutation of the n vertices of a connected graph G. Define δ_α(G) to be the number , where the sum is over all the unordered pairs of distinct vertices of G. The number δ_α(G) is called the total relative displacement of α (in G). So, permutation α is an automorphism of G if and only if δ_α(G) = 0. Let π(G) denote the smallest positive value of δ_α(G) among the n! permutations α of the vertices of G. A permutation α for which π(G) = δ_α(G) has been called a near‐automorphism of G [ 2 ]. We determine π(K) and describe permutations α of K for which π(K) = δ_α(K). This is done by transforming the problem into the combinatorial optimization problem of maximizing the sums of the squares of the entries in certain t by t matrices with non–negative integer entries in which the sum of the entries in the ith row and the sum of the entries in the ith column each equal to n_i,1≤i≤t. We prove that for positive integers, n₁≤n₂≤…≤n_t, where t≥2 and n_t≥2, where k₀ is the smallest index for which n = n+1. As a special case, we correct the value of π(K_m,n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt [ 2 ]. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 85–100, 2002     

Convergence of boundary optimal controls in mixed elliptic problems

We consider a steady-state heat conduction problem P_α withmixed boundary conditions for the Poisson equation in a bounded multidimensional domain Ω depending of a positive parameter α which represents the heat transfer coefficient on a portion Γ₁ of the boundary of Ω. We consider, for each α > 0, a cost function J_α and we formulate boundary optimal control problems with restrictions over the heat flux q on a complementary portion Γ₂ of the boundary of Ω. We obtain that the optimality conditions are given by a complementary free boundary problem in Γ₂ in terms of the adjoint state. We prove that the optimal control q and its corresponding system state u and adjoint state p for each α are strongly convergent to q_op, u and p in L²(Γ₂), H¹(Ω), and H¹(Ω) respectively when α → ∞. We also prove that these limit functions are respectively the optimal control, the system state and the adjoint state corresponding to another boundary optimal control problem with restrictions for the same Poisson equation with a different boundary condition on the portion Γ₁. We use the elliptic variational inequality theory in order to prove all the strong convergences. In this paper, we generalize the convergence result obtained in Ben Belgacem-El Fekih-Metoui, ESAIM:M2AN, 37 (2003), 833-850 by considering boundary optimal control problems with restrictions on the heat flux q defined on Γ₂ and the parameter α (which goes to infinity) is defined on Γ₁. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Lp–Lq maximal regularity for the linear thermoelastic plate equation in a bounded domain

This paper is concerned with the thermoelastic plate equations in a domain Ω: subject to the boundary condition: u|=D_νu|=θ|=0 and initial condition: (u, u_t, θ)|_t=0=(u₀, v₀, θ₀). Here, Ω is a bounded domain in ?ⁿ(n≧2). We assume that the boundary ?Ω of Ω is a C⁴ hypersurface. We obtain an L_p–L_q maximal regularity theorem. Copyright © 2008 John Wiley & Sons, Ltd.     

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     

The Calderón approach to an elliptic boundary problem

We consider a boundary problem for an elliptic system in a bounded region Ω ? ?ⁿ and where the spectral parameter is multiplied by a discontinuous weight function ω (x) = diag(ω₁(x), …, ω_N (x)). The problem is considered under limited smoothness assumptions and under an ellipticity with parameter condition. Recently, this problem was studied under the assumption that the ω_j (x)^–1 are essentially bounded in Ω. In this paper we suppose that ω (x) vanishes identically in a proper subregion Ω of Ω and that the ω_j (x)^–1 are essentially bounded in . Then by using methods which are a variant of those used in constructing the Calderón projectors for the boundary Γ of Ω, we shall derive results here which will enable us in a subsequent work to apply the ideas of Calderón to develop the spectral theory associated with the problem under consideration here (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Improved breakdown criterion for einstein vacuum equations in CMC gauge

Let ${\cal M}_*$ = ∪ Σ_t be a part of vacuum globally hyperbolic space‐time ( M , g ), foliated by constant mean curvature hypersurfaces Σ_t with t₀ < t_* < 0. We improve the existing breakdown criteria for Einstein vacuum equations by showing that the foliation can be extended beyond t_* provided the second fundamental form k and the lapse function n satisfy the weaker condition The proof of this result %in particular relies on the second main result of the paper, which gives a uniform lower bound on the null radius of injectivity. © 2011 Wiley Periodicals, Inc.     

Reversible and DRAD difference sets in

The existence of Hadamard difference sets has been a central question in design theory. Reversible difference sets have been studied extensively. Dillon gave a method for finding reversible difference sets in groups of the form (C)². DRAD difference sets are a newer concept. Davis and Polhill showed the existence of DRAD difference sets in the same groups as Dillon. This article determines the existence of reversible and DRAD difference sets in groups of the form (C)³. These are the only abelian 2‐groups outside of direct products of C₄ and (C)² known to contain reversible and DRAD difference sets. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:58–67, 2012     

New partial difference sets in p‐groups

Latin square type partial difference sets (PDS) are known to exist in R × R for various abelian p‐groups R and in ?^t. We construct a family of Latin square type PDS in ?^t × ?^2nt_p using finite commutative chain rings. When t is odd, the ambient group of the PDS is not covered by any previous construction. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 394–402, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10029     

Strong solutions to the Keller‐Segel system with the weak Ln /2 initial data and its application to the blow‐up rate

We shall show an exact time interval for the existence of local strong solutions to the Keller‐Segel system with the initial data u₀ in L^{n /2}_w (?ⁿ), the weak L^{n /2}‐space on ?ⁿ. If ‖u₀‖ is sufficiently small, then our solution exists globally in time. Our motivation to construct solutions in L^{n /2}_w (?ⁿ) stems from obtaining a self‐similar solution which does not belong to any usual L^p(?ⁿ). Furthermore, the characterization of local existence of solutions gives us an explicit blow‐up rate of ‖u (t)‖ for n /2 < p < ∞ as t → T_max, where T_max denotes the maximal existence time (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Nowhere‐zero flows in tensor product of graphs

In this paper, we characterize graphs whose tensor product admit nowhere‐zero 3‐flow. The main result is: For two graphs G₁ and G₂ with δ ≥ 2 and G₂ not belonging to a well‐characterized class of graphs, the tensor product of G₁ and G₂ admits a nowhere‐zero 3‐flow. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 284–292, 2007     

Universal robustness of scale‐free networks against cascading edge failures

Considering the effect of the local topology structure of an edge on cascading failures, we investigate the cascading reaction behaviors on scale‐free networks with respect to small edge‐based initial attacks. Adopt the initial load of an edge ij in a network to be L_ij = (k_ik_j)^α[(∑k_a)(∑k_b)]^β with k_i and k_j being the degrees of the nodes connected by the edge ij, where α and β are tunable parameters, governing the strength of the edge initial load, and Γ_i and Γ_j are the sets of neighboring nodes of i and j, respectively. Our aim is to explore the relationship between some parameters and universal robustness characteristics against cascading failures on scale‐free networks. We find by the theoretical analysis that the Baraba'si‐Albert (BA) scale‐free networks can reach the strongest robustness level against cascading failures when α + β = 1, where the robustness is quantified by a transition from normal state to collapse. And the network robustness has a positive correlation with the average degree. We furthermore confirm by the numerical simulations these results.     

The existence of positive solutions to a non‐local singular boundary value problem

We consider the non‐local singular boundary value problem (1) where q ∈ C⁰([0,1]) and f, h ∈ C⁰((0,∞)), limf(x)=?∞, limh(x)=∞. We present conditions guaranteeing the existence of a solution x ∈ C¹([0,1]) ∩ C²((0,1]) which is positive on (0,1]. The proof of the existence result is based on regularization and sequential techniques and on a non‐linear alternative of Leray–Schauder type. Copyright © 2005 John Wiley & Sons, Ltd.     

The structure of compact disjointness preserving operators on continuous functions

Let T be a compact disjointness preserving linear operator from C₀(X) into C₀(Y), where X and Y are locally compact Hausdorff spaces. We show that T can be represented as a norm convergent countable sum of disjoint rank one operators. More precisely, T = Σ_n δ ?h_n for a (possibly finite) sequence {x_n }_n of distinct points in X and a norm null sequence {h_n }_n of mutually disjoint functions in C₀(Y). Moreover, we develop a graph theoretic method to describe the spectrum of such an operator (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A new construction of perfect nonlinear functions using Galois rings

For a prime p, we give a construction of perfect nonlinear functions from ? to ? when either of the following conditions holds: (1) n≥p; (2) n<p, and n is a composite number or is the sum of positive composite numbers. It follows that when n≥12, there is a perfect nonlinear function from ? to ? for any prime p. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 229‐239, 2009     

Edge-colored saturated graphs

A graph G is (k₁, k₂, …, k_t)-saturated if there exists a coloring C of the edges of G in t colors 1, 2, …, t in such a way that there is no monochromatic complete k_i-subgraph K of color i, 1 ? i ? t, but the addition of any new edge of color i, joining two nonadjacent vertices in G, with C, creates a monochromatic K of color i, 1 ? i ? t. We determine the maximum and minimum number of edges in such graphs and characterize the unique extremal graphs.     

Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method

The biplanar crossing number cr₂(G) of a graph G is min{cr(G₁) + cr(G₂)}, where cr is the planar crossing number. We show that cr₂(G) ≤ (3/8)cr(G). Using this result recursively, we bound the thickness by Θ(G) ‐ 2 ≤ Kcr₂(G)^0.4057 log₂n with some constant K. A partition realizing this bound for the thickness can be obtained by a polynomial time randomized algorithm. We show that for any size exceeding a certain threshold, there exists a graph G of this size, which simultaneously has the following properties: cr(G) is roughly as large as it can be for any graph of that size, and cr₂(G) is as small as it can be for any graph of that size. The existence is shown using the probabilistic method. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008