The spum and sum-diameter of graphs: Labelings of sum graphs

A sum graph is a finite simple graph whose vertex set is labeled with distinct positive integers such that two vertices are adjacent if and only if the sum of their labels is itself another label. The spum of a graph G is the minimum difference between the largest and smallest labels in a sum graph consisting of G and the minimum number of additional isolated vertices necessary so that a sum graph labeling exists. We investigate the spum of various families of graphs, namely cycles, paths, and matchings. We introduce the sum-diameter, a modification of the definition of spum that omits the requirement that the number of additional isolated vertices in the sum graph is minimal, which we believe is a more natural quantity to study. We then provide asymptotically tight general bounds on both sides for the sum-diameter, and study its behavior under numerous binary graph operations as well as vertex and edge operations. Finally, we generalize the sum-diameter to hypergraphs.     

Robust dimension reduction,fusion frames,and Grassmannian packings

We consider estimating a random vector from its measurements in a fusion frame, in presence of noise and subspace erasures. A fusion frame is a collection of subspaces, for which the sum of the projection operators onto the subspaces is bounded below and above by constant multiples of the identity operator. We first consider the linear minimum mean-squared error (LMMSE) estimation of the random vector of interest from its fusion frame measurements in the presence of additive white noise. Each fusion frame measurement is a vector whose elements are inner products of an orthogonal basis for a fusion frame subspace and the random vector of interest. We derive bounds on the mean-squared error (MSE) and show that the MSE will achieve its lower bound if the fusion frame is tight. We then analyze the robustness of the constructed LMMSE estimator to erasures of the fusion frame subspaces. We limit our erasure analysis to the class of tight fusion frames and assume that all erasures are equally important. Under these assumptions, we prove that tight fusion frames consisting of equi-dimensional subspaces have maximum robustness (in the MSE sense) with respect to erasures of one subspace among all tight fusion frames, and that the optimal subspace dimension depends on signal-to-noise ratio (SNR). We also prove that tight fusion frames consisting of equi-dimensional subspaces with equal pairwise chordal distances are most robust with respect to two and more subspace erasures, among the class of equi-dimensional tight fusion frames. We call such fusion frames equi-distance tight fusion frames. We prove that the squared chordal distance between the subspaces in such fusion frames meets the so-called simplex bound, and thereby establish connections between equi-distance tight fusion frames and optimal Grassmannian packings. Finally, we present several examples for the construction of equi-distance tight fusion frames.     

Generation of finite tight frames by Householder transformations

Finite tight frames are widely used for many applications. An important problem is to construct finite frames with prescribed norm for each vector in the tight frame. In this paper we provide a fast and simple algorithm for such a purpose. Our algorithm employs the Householder transformations. For a finite tight frame consisting of m vectors in ?ⁿ or ?ⁿ only O(nm) operations are needed. In addition, we also study the following question: Given a set of vectors in ?ⁿ or ?ⁿ, how many additional vectors, possibly with constraints, does one need to add in order to obtain a tight frame?     

A note on equal unions in families of sets

A family of sets has the equal union property if and only if there exist two nonempty disjoint subfamilies having the same union. We prove that any n nonempty subsets of an n-element set have the equal union property if the sum of their cardinalities exceeds n(n+1)/2. This bound is tight. Among families in which the sum of the cardinalities equals n(n+1)/2, we characterize those having the equal union property.     

Effective conductivity of a random suspension of highly conducting spherical particles

Randomly distributed non-overlapping perfectly conducting spheres are embedded in a conducting matrix with the concentration of inclusions f. Jeffrey (1973) suggested an analytical formula valid up to O(f³) for macroscopically isotropic random composites. A conditionally convergent sum arose in the spatial averaging. In the present paper, we apply a method of functional equations to random composites and correct Jeffrey’s formula. The main revision concerns the proper investigation of the conditionally convergent sum and correction the f²-term. An algorithm for symbolic computations of the effective conductivity tensor is developed and performed up to $O\left(f^{\frac{10}{3}}\right)$. The obtained formulae explicitly demonstrate the dependence of the effective conductivity tensor on the deterministic and probabilistic distributions of inclusions in the f²-term, and in the f³-term. This leads to the conclusion that some previous formulae presented as universal, i.e., valid for all random composites, may be actually applied only to dilute or to special composites when interaction between inclusions do not matter.     

Quantitative relation between noise sensitivity and influences

A Boolean function f: {0,1} ⁿ → {0,1} is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm [3] showed that if the sum of squares of inuences of f is close to zero then f must be noise sensitive. We show a quantitative version of this result which does not depend on n, and prove that it is tight for certain parameters. Our results hold also for a general product measure µ _p on the discrete cube, as long as log1/p?logn. We note that in [3], a quantitative relation between the sum of squares of the inuences and the noise sensitivity was also shown, but only when the sum of squares is bounded by n ^?c for a constant c. Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions. In order to achieve it, we present a considerably shorter proof of Talagrand’s lemma, which easily generalizes in various directions, including non-monotone functions.     

The class A(R,S) of (0, 1)-matrices

Let R and S be two vectors whose components are m and n non-negative integers, respectively. Let $\text{A}$(R, S) be the class consisting of all (0, 1)-matrices of size m by n with row sum vector R and column sum vector S. In this paper we derive a lower bound to the cardinality of the class $\text{A}$(R, S), which can be computed readily.     

Compactly supported multiwindow dual Gabor frames of rational sampling density

We consider multiwindow Gabor systems (G _N ; a, b) with N compactly supported windows and rational sampling density N/ab. We give another set of necessary and sufficient conditions for two multiwindow Gabor systems to form a pair of dual frames in addition to the Zibulski–Zeevi and Janssen conditions. Our conditions come from the back transform of Zibulski–Zeevi condition to the time domain but are more informative to construct window functions. For example, the masks satisfying unitary extension principle (UEP) condition generate a tight Gabor system when restricted on [0, 2] with a?=?1 and b?=?1. As another application, we show that a multiwindow Gabor system (G _N ; 1, 1) forms an orthonormal basis if and only if it has only one window (N?=?1) which is a sum of characteristic functions whose supports ‘essentially’ form a Lebesgue measurable partition of the unit interval. Our criteria also provide a rich family of multiwindow dual Gabor frames and multiwindow tight Gabor frames for the particular choices of lattice parameters, number and support of the windows. (Section 4)     

On a new system of nonlinear A-monotone multivalued variational inclusions

In this paper, we introduce and study a new system of nonlinear A-monotone multivalued variational inclusions in Hilbert spaces. By using the concept and properties of A-monotone mappings, and the resolvent operator technique associated with A-monotone mappings due to Verma, we construct a new iterative algorithm for solving this system of nonlinear multivalued variational inclusions associated with A-monotone mappings in Hilbert spaces. We also prove the existence of solutions for the nonlinear multivalued variational inclusions and the convergence of iterative sequences generated by the algorithm. Our results improve and generalize many known corresponding results.     

On Tight Spans for Directed Distances

An extension (V, d) of a metric space (S,???) is a metric space with ${{S \subseteq V}}$ and ${{d\mid{_S} = \mu}}$ , and is said to be tight if there is no other extension (V, d??) of (S,???) with d?? ???d . Isbell and Dress independently found that every tight extension embeds isometrically into a certain metrized polyhedral complex associated with (S,???), called the tight span. This paper develops an analogous theory for directed metrics, which are ??not necessarily symmetric?? distance functions satisfying the triangle inequality. We introduce a directed version of the tight span and show that it has a universal embedding property for tight extensions. Also we introduce a new natural class of extensions, called cyclically tight extensions, and we show that there also exists a certain polyhedral complex having a universal property relative to cyclically tightness. This polyhedral complex coincides with (a fiber of) the tropical polytope spanned by the column vectors of ?C??, which was earlier introduced by Develin and Sturmfels. Thus this gives a tight-span interpretation to the tropical polytope generated by a nonnegative square matrix satisfying the triangle inequality. As an application, we prove the following directed version of the tree metric theorem: A directed metric??? is a directed tree metric if and only if the tropical rank of ?C?? is at most two. Also we describe how tight spans and tropical polytopes are applied to the study of multicommodity flows in directed networks.     

Lie triple derivation of the Lie algebra of strictly upper triangular matrix over a commutative ring

Let N(n,R) be the nilpotent Lie algebra consisting of all strictly upper triangular n×n matrices over a 2-torsionfree commutative ring R with identity 1. In this paper, we prove that any Lie triple derivation of N(n,R) can be uniquely decomposited as a sum of an inner triple derivation, diagonal triple derivation, central triple derivation and extremal triple derivation for n≧6. In the cases 1≦n≦5, the results are trivial.     

A Bifurcation of Solutions of Nonlinear Fredholm Inclusions Involving CJ-Multimaps with Applications to Feedback Control Systems

In this paper, by applying the oriented coincidence index for a pair consisting of a nonlinear Fredholm operator and a CJ-multimap, we prove a global bifurcation theorem for solutions of families of inclusions with such maps. The method of guiding functions is used to calculate the oriented coincidence index for a class of feedback control systems. This characteristic allows to obtain the existence result for periodic trajectories of such systems. From the other side, it opens the possibility to apply the abstract bifurcation result to the study of qualitative behavior of branches of periodic trajectories.     

The Path-Connectivity of s-Elementary Frame Wavelets with Frame MRA

MRA wavelets have been widely studied in recent years due to their applications in signal processing. In order to understand the properties of the various MRA wavelets, it makes sense to study the topological structure of the set of all MRA wavelets. In fact, it has been shown that the set of all MRA wavelets (in any given dimension with a fixed expansive dilation matrix) is path-connected. The current paper concerns a class of functions more general than the MRA wavelets, namely normalized tight frame wavelets with a frame MRA structure. More specifically, it focuses on the parallel question on the topology of the set of all such functions (in the given dimension with a fixed dilation matrix): is this set path-connected? While we are unable to settle this general path-connectivity problem for the set of all frame MRA normalized tight frame wavelets, we show that this holds for a subset of it. An s-elementary frame MRA normalized tight frame wavelets (associated with a given expansive matrix A as its dilation matrix) is a normalized tight frame wavelet whose Fourier transform is of the form $\frac{1}{\sqrt{2\pi}}\chi_{E}$ for some measurable set E?? ^d . In this paper, we show that for any given d×d expansive matrix A, the set of all (A-dilation) s-elementary normalized tight frame wavelets with a frame MRA structure is also path-connected.     

On the nonexistence of nontrivial perfecte-codes and tight 2e-designs in hamming schemesH(n,q) withe ≥ 3 andq ≥ 3

It is known that if there exist perfecte-codes or tight 2e-designs in a Hamming schemeH(n, q), then all the zeros of the Lloyd polynomial $$F_e \left( x \right) = \sum\limits_{i = 0}^e {\left( { - q} \right)^i \left( {q - 1} \right)^{e - i} } \left( {\begin{array}{*{20}c} {n - i - 1} \\ {e - i} \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {x - 1} \\ i \\ \end{array} } \right)$$ are integers in the interval [1,n]. With some results of Best, we show that ife ≥ 3,n ≥ e + 1, andq ≥ 3, thenF _e (x) has a nonintegral zero. Therefore there exist no nontrivial perfecte-codes and tight 2e-designs inH(n,q) ife ≥ 3 andq ≥ 3.     

Principal Γ-cone for a tree

For any tree Γ, we introduce Γ-cones consisting of chambers and enumerate the number of chambers contained in two particular (called principal) Γ-cones. The problem is equivalent to the combinatorial problem of the enumeration of linear extensions of two bipartite orderings on a tree Γ. We characterize the principal Γ-cones among other Γ-cones by the strict maximality of the number of their chambers, and give a formula for this maximal (called principal) number by a finite sum of hook length formulae. We explain the formula through the simplicial block decomposition of principal Γ-cones. The results have their origin and application in the study of the topology related to Coxeter groups and Artin groups.     

Fast approximation algorithm for job sequencing with deadlines

The problem under consideration is to schedule jobs on a machine in order to minimize the sum of the penalties of delayed jobs. A “range-and-bound” method is proposed for finding a tight bound P? such that P?≤P1≤2P?, P1 being the minimal sum desired. The considered scheduling problem, for n jobs and accuracy ε > 0, is solved by a fully polynomial ε-approximation algorithm in $\text{O(n}{}^2\text{log n +}\text{n}{}^2\text{ε}\text{)}$ time and $\text{O(}\text{n}{}^2\text{ε}\text{)}$ space.     

Three-step iterative methods for general variational inclusions in L P spaces

In this paper, we show that the general variational inclusions are equivalent to the fixed point problem. We use this equivalence to discuss the existence of the variational inclusions in L ^p spaces. Using the technique of the updating solution, we suggest some three-step iterative methods for solving the general variational inclusion. We also consider the convergence analysis of the proposed iterative methods under some mild conditions. Since the general variational inclusions include several classes of variational inequalities and optimization problems as special cases, results proved in this paper continue to hold for these problems.     

Newton-Like Dynamics and Forward-Backward Methods for Structured Monotone Inclusions in Hilbert Spaces

In a Hilbert space setting we introduce dynamical systems, which are linked to Newton and Levenberg–Marquardt methods. They are intended to solve, by splitting methods, inclusions governed by structured monotone operators M=A+B, where A is a general maximal monotone operator, and B is monotone and locally Lipschitz continuous. Based on the Minty representation of A as a Lipschitz manifold, we show that these dynamics can be formulated as differential systems, which are relevant to the Cauchy–Lipschitz theorem, and involve separately B and the resolvents of A. In the convex subdifferential case, by using Lyapunov asymptotic analysis, we prove a descent minimizing property and weak convergence to equilibria of the trajectories. Time discretization of these dynamics gives algorithms combining Newton’s method and forward-backward methods for solving structured monotone inclusions.     

Extremal Systems with Upper-Bounded Odd Intersections

In this paper we determine the maximum cardinality m of a family A= {A ₁,..., A _m} of subsets of a set of n elements with the property that for each A _i there are at most s A _j such that |A _i ∩ A _j | is odd (even). A tight upper bound is given in the case s < c(2 ^n,2/n). In the remaining cases we give an asymptotically tight upper bound. As an application we give a tight upper-bound for the cardinality of a family with even multi-intersection. Both results generalize a result of Berlekamp and Graver.     

On the eccentric distance sum of graphs

The eccentric distance sum is a novel topological index that offers a vast potential for structure activity/property relationships. For a graph G, it is defined as ξd(G)=_∑v∈Vε(v)D(v), where ε(v) is the eccentricity of the vertex v and D(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. Motivated by [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 934-944], in this paper we characterize the extremal trees and graphs with maximal eccentric distance sum. Various lower and upper bounds for the eccentric distance sum in terms of other graph invariants including the Wiener index, the degree distance, eccentric connectivity index, independence number, connectivity, matching number, chromatic number and clique number are established. In addition, we present explicit formulae for the values of eccentric distance sum for the Cartesian product, applied to some graphs of chemical interest (like nanotubes and nanotori).