Three characterizations of non-binary correlation-immune and resilient functions

A functionf(X ₁,X ₂, ...,X _n ) is said to betth-order correlation-immune if the random variableZ=f(X ₁,X ₂,...,X _n ) is independent of every set oft random variables chosen from the independent equiprobable random variablesX ₁,X ₂,...,X _n . Additionally, if all possible outputs are equally likely, thenf is called at-resilient function. In this paper, we provide three different characterizations oft th-order correlation immune functions and resilient functions where the random variable is overGF (q). The first is in terms of the structure of a certain associated matrix. The second characterization involves Fourier transforms. The third characterization establishes the equivalence of resilient functions and large sets of orthogonal arrays.     

Multidimensional Oscillations for Non-linear Hyperbolic Mixed Problem: The Justified Non-linear Geometric Optics Method

The mixed-Neumann problem for the non-linear wave equation □u−a(u)(∣∂_tu)∣²−∣∇u∣² = f_ε(z) is studied. The function f_ε(z) = ∑_k∈Kf_k(z,ε⁻¹ϕ_k(z),ε), ε∈[0,1], K is finite, f_k(z,θ_k,ε) are 2π-periodic with respect to θ_k. The existence of solution u_ε on a domain z = (t,x,y)∈[0,T]×ℝ₊×ℝ^d, d = 1 or 2, is proved when ε is sufficiently small; T does not depend on ε. By the non-linear geometric optics method the asymptotic (with respect to ε→0) solution ũ _ε is constructed. The estimation for the rest ε²r_ε = u_ε−ũ_ε is derived and the limit r_ε, ε→0, is studied.     

Large deviation for the empirical eigenvalue density of truncated Haar unitary matrices

Let U_m be an m×m Haar unitary matrix and U_[m,n] be its n×n truncation. In this paper the large deviation is proven for the empirical eigenvalue density of U_[m,n] as m/n→λ and n→∞. The rate function and the limit distribution are given explicitly. U_[m,n] is the random matrix model of quq, where u is a Haar unitary in a finite von Neumann algebra, q is a certain projection and they are free. The limit distribution coincides with the Brown measure of the operator quq.     

The Superlinear Convergence of a Modified BFGS-Type Method for Unconstrained Optimization

The BFGS method is the most effective of the quasi-Newton methods for solving unconstrained optimization problems. Wei, Li, and Qi [16] have proposed some modified BFGS methods based on the new quasi-Newton equation B _k+1 s _k = y* _k , where y* _k is the sum of y _k and A _k s _k, and A _k is some matrix. The average performance of Algorithm 4.3 in [16] is better than that of the BFGS method, but its superlinear convergence is still open. This article proves the superlinear convergence of Algorithm 4.3 under some suitable conditions.     

Decomposition of bipartite graphs into closed trails

Let Lct(G) denote the set of all lengths of closed trails that exist in an even graph G. A sequence (t ₁,..., t _p ) of elements of Lct(G) adding up to |E(G)| is G-realisable provided there is a sequence (T ₁,..., t _p ) of pairwise edge-disjoint closed trails in G such that T _i is of length T _i for i = 1,..., p. The graph G is arbitrarily decomposable into closed trails if all possible sequences are G-realisable. In the paper it is proved that if a ⩾ 1 is an odd integer and M _a,a is a perfect matching in K _a,a , then the graph K _a,a -M _a,a is arbitrarily decomposable into closed trails.      

Optimal Systems and Group Classification of (1+2)-Dimensional Heat Equation

The optimal systems and symmetry breaking interactions for the (1+2)-dimensional heat equation are systematically studied. The equation is invariant under the nine-dimensional symmetry group H ₂. The details of the construction for an one-dimensional optimal system is presented. The optimality of one- and two-dimensional systems is established by finding some algebraic invariants under the adjoint actions of the group H ₂. A list of representatives of all Lie subalgebras of the Lie algebra h ₂ of the Lie group H ₂ is given in the form of tables and many of their properties are established. We derive the most general interactions F(t,x,y,u,u _x ,u _y ) such that the equation u _t =u _xx +u _yy +F(t,x,y,u,u _x ,u _y ) is invariant under each subgroup.     

Representations of the Quantum Algebra Uq(un, 1)

The main aim of the paper is to study infinite-dimensional representations of the real form U _q (u _{n, 1}) of the quantized universal enveloping algebra U _q (gl _{n + 1}). We investigate the principal series of representations of U _q (u _{n, 1}) and calculate the intertwining operators for pairs of these representations. Some of the principal series representations are reducible. The structure of these representations is determined. Then we classify irreducible representations of U _q (u _{n, 1}) obtained from irreducible and reducible principal series representations. All *-representations in this set of irreducible representations are separated. Unlike the classical case, the algebra U _q (u _{n, 1}) has finite-dimensional irreducible *-representations.     

Line graphs of bipartite graphs with Hamiltonian paths

It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path P_t as a star complement for the eigenvalue ?2. The maximal graph is the line graph of K_m,m if t = 2m?1, and of K_m,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement P_r ∪ P_s or P_r ∪ C_s for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003     

Thek-partitioning problem

Thek-partitioning problem is defined as follows: Given a set of items {I ₁,I ₂,...,I _n} where itemIj is of weightwj 0, find a partitionS ₁,S ₂,...,S _m of this set with ¦S _i ¦ =k such that the maximum weight of all subsetsS _i is minimal,k-partitioning is strongly related to the classical multiprocessor scheduling problem of minimizing the makespan on identical machines. This paper provides suitable tools for the construction of algorithms which solve exactly the problem. Several approximation algorithms are presented for this NP-hard problem. The worst-case behavior of the algorithms is analyzed. The best of these algorithms achieves a performance bound of 4/3.     

A Parallel Algorithm for the Estimation of the Global Error in Runge–Kutta Methods

The object of this work is the estimate of the global error in the numerical solution of the IVP for a system of ODE's. Given a Runge–Kutta formula of order q, which yields an approximation y _n to the true value y(x _n ), a general, parallel method is presented, that provides a second value y _n ^* of order q+2; the global error e _n =y _n –y(x _n ) is then estimated by the difference y _n –y _n ^*. The numerical tests reported, show the very good performance of the procedure proposed. A comparison with the code GEM90 is also appended.     

The Largest Left Quotient Ring of a Ring

The left quotient ring (i.e., the left classical ring of fractions) Q_cl(R) of a ring R does not always exist and still, in general, there is no good understanding of the reason why this happens. In this article, existence of the largest left quotient ring Q_l(R) of an arbitrary ring R is proved, i.e., Q_l(R) = S₀(R)^?1R where S₀(R) is the largest left regular denominator set of R. It is proved that Q_l(Q_l(R)) = Q_l(R); the ring Q_l(R) is semisimple iff Q_cl(R) exists and is semisimple; moreover, if the ring Q_l(R) is left Artinian, then Q_cl(R) exists and Q_l(R) = Q_cl(R). The group of units Q_l(R)* of Q_l(R) is equal to the set {s^?1t | s, t ∈ S₀(R)} and S₀(R) = R ∩ Q_l(R)*. If there exists a finitely generated flat left R-module which is not projective, then Q_l(R) is not a semisimple ring. We extend slightly Ore's method of localization to localizable left Ore sets, give a criterion of when a left Ore set is localizable, and prove that all left and right Ore sets of an arbitrary ring are localizable (not just denominator sets as in Ore's method of localization). Applications are given for certain classes of rings (semiprime Goldie rings, Noetherian commutative rings, the algebra of polynomial integro-differential operators).     

Rank properties of certain semigroups

In this paper we consider certain ranks of some semigroups. These ranks are r ₁(S),r ₂(S),r ₃(S),r ₄(S) and r ₅(S) as defined below. We have r ₁≤r ₂≤r ₃≤r ₄≤r ₅. The semigroups are CL _n ,CL _m ×CL _n ,Z _n and SL _n . Here CL _n is a chain with n elements, Z _n is the zero semigroup on n elements and SL _n is the free semilattice generated by n elements and having 2 ⁿ −1 elements. We find many of the ranks for these classes of semigroups.     

On some extremal problems in graph theory

The author proves that ifC is a sufficiently large constant then every graph ofn vertices and [Cn ^3/2] edges contains a hexagonX ₁,X ₂,X ₃,X ₄,X ₅,X ₆ and a seventh vertexY joined toX ₁,X ₃ andX ₅. The problem is left open whether our graph contains the edges of a cube, (i.e. an eight vertexZ joined toX ₂,X ₄ andX ₆).     

Infinite products for power series

An algorithm is introduced and shown to lead to a unique infinite product representation for a given formal power series A(z) with A(0) = 1. The infinite product is , where all b_n ≠ 0, r_n , and r_n+1 > r_n. The degree of approximation by the polynomial (1 + b₁z^r₁) · · · (1 + b_nz^r_n) is also considered.     

Failure of cancellation conditions for additive linear orders

Coordinate independence assumptions, also known as cancellation conditions, play a central role in the representational theory of measurement for an ordering relation ≻ on a finite Cartesian product set A₁ × A₂ × ··· × A_m. A sequence of increasingly complex cancellation conditions is known to be sufficient for additive representability in the form (a₁, a₂, ⋖ a_m) ≻ (b₁, b₂, ⋖ b_m) ⇔ ∑_i v(a_i) > &sum_i v(b_i). A longstanding open problem is to determine the simplest subset of cancellation conditions as a function of the size of A₁ × ··· × A_m that is violated by every order ≻ that is not additively representable. This article proves a lower bound on minimum subset sufficiency when all A_i are binary. We conjecture that this lower bound, which is very near to a known upper bound, is the exact minimum. The binary-factors version of the problem is reformulated under a first-order independence assumption by a map from ≻ on {0,1}^m into a subset L of {1,0,−1}^m that is referred to as an additive linear order. The lower bound is then established by examples of additive linear orders on {1,0,−1}^m that exhibit worst-case failures of cancellation. © 1997 John Wiley & Sons, Inc. J Combin Designs 5:353–365, 1997     

Some intriguing upper bounds for separating hash families

An N ×n matrix on q symbols is called {w_1,...,w_t}-separating if for arbitrary t pairwise disjoint column sets C_1,..., C_t with |C_i|=w_i for 1 ≤i≤t, there exists a row f such that f(C_1),...,f(C_t) are also pairwise disjoint, where f(C_i) denotes the collection of componentn of C_i restricted to row f. Given integers N, q and w_1,...,w_t, denote by C(N,q,{w_1,...,w_t}) the maximal a such that a corresponding matrix does exist.The determination of C(N,q,{w_1,...,w_t}) has received remarkable attention during the recent years. The main purpose of this paper is to introduce two novel methodologies to attack the upper bound of C(N, q, {w_1,...,w_t}).The first one is a combination of the famous graph removal lemma in extremal graph theory and a Johnson-type recursive inequality in coding theory, and the second onc is the probabilistic method. As a consequence, we obtain several intriguing upper bounds for some parameters of C(N,q,{w_1,...,w_t}), which significantly improve the previously known results.     

Gotzmann Edge Ideals

Let P = 𝕜[x ₁,…, x _n ] be the polynomial ring in n variables. A homogeneous ideal I ? P generated in degree d is called Gotzmann if it has the smallest possible Hilbert function out of all homogeneous ideals with the same dimension in degree d. The edge ideal of a simple graph G on vertices x ₁,…, x _n is the quadratic square-free monomial ideal generated by all x _i x _j where {x _i , x _j } is an edge of G. The only edge ideals that are Gotzmann are those edge ideals corresponding to star graphs.     

Going in Circles: Variations on the Money-Coutts Theorem

Given a polygon A ₁,...,A _n, consider the chain of circles: S ₁ inscribed in the angle A ₁, S ₂ inscribed in the angle A ₂ and tangent to S ₁, S ₃ inscribed in the angle A ₃ and tangent to S ₂, etc. We describe a class of n-gons for which this process is 2n-periodic. We extend the result to the case when the sides of a polygon are arcs of circles. The case of triangles is known as the Money-Coutts theorem.     

When the cartesian product of directed cycles is Hamiltonian

The cartesian product of two hamiltonian graphs is always hamiltonian. For directed graphs, the analogous statement is false. We show that the cartesian product C_n1 × C_n2 of directed cycles is hamiltonian if and only if the greatest common divisor (g.c.d.) d of n₁ and n₂ is at least two and there exist positive integers d₁, d₂ so that d₁ + d₂ = d and g.c.d. (n₁, d₁) = g.c.d. (n₂, d₂) = 1. We also discuss some number-theoretic problems motivated by this result.     

Ki-covers. II. Ki-perfect graphs

AK_i is a complete subgraph of size i. A K_i-cover of a graph G(V, E) is a set C of K_i?1s of G such that every K_i in G contains at least one K_i?1 in C . c_i(G) is the cardinality of a smallest K_i-cover of G. A K_i-packing of G is a set of K_is such that no two K_is have i ? 1 nodes in common. p_i(G) is the cardinality of a largest K_i-packing of G. Let F _i(G) denote the set of K_is in G and define c_i(F) and p_i(F) analogously for F ? F _i(G). G is K_i-perfect if ?F ? F _i(G), c_i(F) = p_i(F). The K₂-perfect graphs are precisely the bipartite graphs. We present a characterization of K_i-perfect graphs that is similar to the Strong Perfect Graph Conjecture, and explore the relationships between K_i-perfect graphs and normal hypergraphs. Furthermore, if iA denotes the 0 ? 1 matrix of G where the rows are the elements of F _i?1(G) that belong to at least one K_i and the columns are the elements of F _i(G), then we show that iA is perfect iff G is a K_i-perfect graph. We also characterize the K_i-perfect graphs for which iAis balanced.