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.     

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     

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)     

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     

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.     

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     

Behavior of the constant in Korenblum's maximum principle

Let A^p (??) (p ≥ 1) be the Bergman space over the open unit disk ?? in the complex plane. Korenblum's maximum principle states that there is an absolute constant c ∈ (0, 1) (may depend on p), such that whenever |f (z)| ≤ |g (z)| (f, g ∈ A^p (??)) in the annulus c < |z | < 1, then ∥f ≤ ∥g ∥. For p ≥ 1, let c_p be the largest value of c for which Korenblum's maximum principle holds. In this note we prove that c_p → 1 as p → ∞. Thus we give a positive answer of a question of Hinkkanen. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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     

Slow emergence of the giant component in the growing m‐out graph

Let H be a random graph on n vertices, grown by adding vertices one at a time, joining each new vertex to a uniformly chosen set of m earlier vertices. If edges of H are deleted independently, each being retained with probability p, then there is a “phase transition”. There is a certain critical value p_c of p such that, with high probability, a component of order Θ(n) remains as n → ∞ if and only if p > p_c. Among other results, we obtain the exact value of p_c, which depends on m in a nontrivial way, and show that the phase transition has “infinite order”; in fact, for p = p_c + ?, the largest component has order exp(?Θ(1/ ))n with high probability. Analogous results were proved recently in by Bollobás, Janson, and Riordan [Random Structures Algorithms 26 (2005), 1–36] for a related model in which edges are present independently. The model we study is considerably more difficult to analyze, since the dependence between the edges is very important, affecting the value of p_c, so many new complications arise. In overcoming these complications we make use of the techniques developed by the authors [Internet Math 1 (2003), 1–35] to analyze a very different model. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

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     

Balancing vectors and Gaussian measures of n-dimensional convex bodies

Let ‖·‖ be the Euclidean norm on R ⁿ and γ_n the (standard) Gaussian measure on R ⁿ with density (2π)^−n/2e. It is proved that there is a numerical constant c>0 with the following property: if K is an arbitrary convex body in R ⁿ with γ_n(K)≥1/2, then to each sequence u₁,…,u_m∈ R ⁿ with ‖u₁‖,…,‖u_m‖≤c there correspond signs ε₁,…,ε_m=±1 such that ∑^m_i=1ε_iu_i∈K. This improves the well-known result obtained by Spencer [Trans. Amer. Math. Soc. 289 , 679–705 (1985)] for the n-dimensional cube. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 351–360, 1998     

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     

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     

On a conjecture on maximal planar sequences

Let d1 d2 dp denote the nonincreasing sequence d₁, …, d₁, d₂, …, d₂, …, d_p, …, d_p, where the term d_i appears k_i times (i = 1, 2, …, p). In this work the author proves that the maximal 2-sequences: 7³6¹5¹⁵, 7⁵6¹5¹⁷, 7⁷6¹5¹⁹ are planar graphical, in contrast to a conjecture by Schmeichel and Hakimi.     

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     

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     

Enumeration of graphs by degree sequence

The degree sequence (d₀, d₁, …, d_p-1) of a graph G of order p is defined by d_k = the number of points of G of degree k. Methods of Robinson are extended to produce a generating function F(x₀, x₁, x₂, …) where the coefficient of x…x is the number of graphs of order p having degree sequence (d₀, …, d_p-1).     

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.     

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)