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.     

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     

Star factorizations of graph products

A k‐star is the graph K_1,k. We prove a general theorem about k‐star factorizations of Cayley graphs. This is used to give necessary and sufficient conditions for the existence of k‐star factorizations of any power (K_q)^s of a complete graph with prime power order q, products C × C ×··· × C of k cycles of arbitrary lengths, and any power (C_r)^s of a cycle of arbitrary length. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 59–66, 2001     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000     

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)     

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)     

Covering arrays with mixed alphabet sizes

Covering arrays with mixed alphabet sizes, or simply mixed covering arrays, are natural generalizations of covering arrays that are motivated by applications in software and network testing. A (mixed) covering array A of type is a k × N array with the cells of row i filled with elements from ? and having the property that for every two rows i and j and every ordered pair of elements (e,f) ∈ ? × ?, there exists at least one column c, 1 ≤ c ≤ N, such that A_i,c = e and A_j,c = f. The (mixed) covering array number, denoted by , is the minimum N for which a covering array of type with N columns exists. In this paper, several constructions for mixed covering arrays are presented, and the mixed covering array numbers are determined for nearly all cases with k = 4 and for a number of cases with k = 5. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 413–432, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10059     

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     

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     

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     

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     

Conditional negative association for competing urns

We prove conditional negative association for random variables x _j = 1 (j∈[n]:= {1…n}) , where σ(1)…σ(m) are i.i.d. from [n]. (The σ(i) 's are thought of as the locations of balls dropped independently into urns 1…n according to some common distribution, so that, for some threshold t_j, x _j is the indicator of the event that at least t_j balls land in urn j.) We mostly deal with the more general situation in which the σ(i) 's need not be identically distributed, proving results which imply conditional negative association in the i.i.d. case. Some of the results—particularly Lemma 8 on graph orientations—are thought to be of independent interest. We also give a counterexample to a negative correlation conjecture of D. Welsh, a strong version of a (still open) conjecture of G. Farr. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Monotone numerical schemes for a Dirichlet problem for elliptic operators in divergence form

We consider a second‐order differential operator A( x )=?∑?_ia_ij( x )?_j+ ∑?_j(b_j( x )·)+c( x ) on ?^d, on a bounded domain D with Dirichlet boundary conditions on ?D, under mild assumptions on the coefficients of the diffusion tensor a_ij. The object is to construct monotone numerical schemes to approximate the solution of the problem A( x )u( x )=µ( x ), x ∈D, where µ is a positive Radon measure. We start by briefly mentioning questions of existence and uniqueness introducing function spaces needed to prove convergence results. Then, we define non‐standard stencils on grid‐knots that lead to extended discretization schemes by matrices possessing compartmental structure. We proceed to discretization of elliptic operators, starting with constant diffusion tensor and ending with operators in divergence form. Finally, we discuss W‐convergence in detail, and mention convergence in C and L₁ spaces. We conclude by a numerical example illustrating the schemes and convergence results. Copyright © 2008 John Wiley & Sons, Ltd.     

Blow‐up rate estimates for a parabolic system with multiple nonlinearities

In this paper, we study the blow‐up behaviors for the solutions of parabolic systems u_t=Δu+δ₁e, v_t=Δv+µ₁u in ?×(0, T) with nonlinear boundary conditions Here δ_i?0, µ_j?0, p_i?0, q_j?0 and at least one of δ_iµ_jp_iq_j>0(i, j=1, 2). We prove that the solutions will blow up in finite time for suitable ‘large’ initial values. The exact blow‐up rates are also obtained. Copyright © 2009 John Wiley & Sons, Ltd.     

Asymptotic spatial homogeneity of solutions to conservation laws with memory in several space dimensions

We prove that any solution of the problem (u+K*u)_t+∑a_i(u)u=0 on (0,∞)×ℝ^N with spatially periodic initial data converges to a constant provided some non-degeneracy conditions on the kernel K and the non-linear functions a_i,i=1,…,N are imposed. © 1997 B. G. Teubner Stuttgart-John Wiley & Sons Ltd.     

Interior numerical approximation of boundary value problems with a distributional data

We study the approximation properties of a harmonic function u ∈ H^1?k(Ω), k > 0, on a relatively compact subset A of Ω, using the generalized finite element method (GFEM). If Ω = ??, for a smooth, bounded domain ??, we obtain that the GFEM‐approximation u_S ∈ S of u satisfies ‖u ? u_S‖ ≤ Ch^γ‖u‖, where h is the typical size of the “elements” defining the GFEM‐space S and γ ≥ 0 is such that the local approximation spaces contain all polynomials of degree k + γ. The main technical ingredient is an extension of the classical super‐approximation results of Nitsche and Schatz (Applicable Analysis 2 (1972), 161–168; Math Comput 28 (1974), 937–958). In addition to the usual “energy” Sobolev spaces H¹(??), we need also the duals of the Sobolev spaces H^m(??), m ∈ ?₊. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

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 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     

A multilevel finite element method in space‐time for the Navier‐Stokes problem

A multilevel finite element method in space‐time for the two‐dimensional nonstationary Navier‐Stokes problem is considered. The method is a multi‐scale method in which the fully nonlinear Navier‐Stokes problem is only solved on a single coarsest space‐time mesh; subsequent approximations are generated on a succession of refined space‐time meshes by solving a linearized Navier‐Stokes problem about the solution on the previous level. The a priori estimates and error analysis are also presented for the J‐level finite element method. We demonstrate theoretically that for an appropriate choice of space and time mesh widths: h_j ～ h, k_j ～ k, j = 2, …, J, the J‐level finite element method in space‐time provides the same accuracy as the one‐level method in space‐time in which the fully nonlinear Navier‐Stokes problem is solved on a final finest space‐time mesh. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

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)