Bursts in m-metric array codes

Fire [P. Fire, A class of multiple-error-correcting binary codes for non-independent errors, Sylvania Reports RSL-E-2, Sylvania Reconnaissance Systems, Mountain View, California, 1959] introduced the concept of bursts for classical codes where codes are subsets/subspaces of the space , the space of all n-tuples with entries from a finite field F_q. In this paper, we introduce the notion of bursts for m-metric array codes where m-metric array codes are subsets/subspaces of the space Mat_m×s(F_q), the linear space of all m × s matrices with entries from a finite field F_q, endowed with a non-Hamming metric. We also obtain some bounds (analogous to Fire’s bound [P. Fire, A class of multiple-error-correcting binary codes for non-independent errors, Sylvania Reports RSL-E-2, Sylvania Reconnaissance Systems, Mountain View, California, 1959], Rieger’s bound [S.H. Reiger, Codes for the correction of clustered errors, IRE-Trans., IT-6 (1960), 16-21] etc. in classical codes) on the parameters of m-metric array codes for the detection and correction of burst errors.     

On forming the Romberg table

Romberg-type extrapolation is commonly used in many areas of numerical computation. An algorithm is presented for forming the Romberg table for general step-length sequence and general powers in the asymptotic expansion. It is then shown that parameters of the algorithm can be used to gain an a priori bound on propagation of rounding errors in the table.     

Superpolynomial Lower Bounds for Monotone Span Programs

monotone span programs computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper. Our lower bounds are based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. We prove an lower bound for the size of monotone span programs for the clique problem. Our results give the first superpolynomial lower bounds for linear secret sharing schemes. We demonstrate the surprising power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. We also show that the perfect matching function can be computed by polynomial size (non-monotone) span programs over arbitrary fields. Received: August 1, 1996     

Model selection by sequentially normalized least squares

Model selection by means of the predictive least squares (PLS) principle has been thoroughly studied in the context of regression model selection and autoregressive (AR) model order estimation. We introduce a new criterion based on sequentially minimized squared deviations, which are smaller than both the usual least squares and the squared prediction errors used in PLS. We also prove that our criterion has a probabilistic interpretation as a model which is asymptotically optimal within the given class of distributions by reaching the lower bound on the logarithmic prediction errors, given by the so called stochastic complexity, and approximated by BIC. This holds when the regressor (design) matrix is non-random or determined by the observed data as in AR models. The advantages of the criterion include the fact that it can be evaluated efficiently and exactly, without asymptotic approximations, and importantly, there are no adjustable hyper-parameters, which makes it applicable to both small and large amounts of data.     

On a Degree Property of Cross-Intersecting Families

Motivated by some applications in computational complexity, Razborov and Vereshchagin proved a degree bound for cross-intersecting families in [1]. We sharpen this result and show that our bound is best possible by constructing appropriate families. We also consider the case of cross-t-intersecting families. Received October 28, 1999     

A sharp upper bound on the maximal entry in the principal eigenvector of symmetric nonnegative matrix

An upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries is investigated in [S. Zhao, Y. Hong, On the bounds of maximal entries in the principal eigenvector of symmetric nonnegative matrix, Linear Algebra Appl. 340 (2002) 245-252]. We obtain a sharp upper bound on the maximal entry y^max_p in the principal eigenvector of symmetric nonnegative matrix in terms of order, the spectral radius, the largest and the smallest diagonal entries of that matrix. Our bound is applicable for any symmetric nonnegative matrix and the upper bound of Zhao and Hong (2002) for the maximal entry y^max_p follows as a special case. Moreover, we find an upper bound on maximal entry in the principal eigenvector for the signless Laplacian matrix of a graph.     

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.     

Lower bound theorem for normal pseudomanifolds

In this paper we present a self-contained combinatorial proof of the lower bound theorem for normal pseudomanifolds, including a treatment of the cases of equality in this theorem. We also discuss McMullen and Walkup's generalized lower bound conjecture for triangulated spheres in the context of the lower bound theorem. Finally, we pose a new lower bound conjecture for non-simply connected triangulated manifolds.     

Families of locally separated Hamilton paths

We improve by an exponential factor the lower bound of Körner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of n vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor.     

An upper bound for the number of Eulerian orientations of a regular graph

We establish a new upper bound for the number of Eulerian orientations of a regular graph with even degrees.C.N.R.S., Paris with partial support of P.R.C. Mathématiques-Informatique.     

The average-case analysis of some on-line algorithms for bin packing

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0, 1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analyzing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem. A preliminary version of this paper appeared inProc. 25th IEEE Symposium on Foundations of Computer Science, 193–200. This research was done while the author was at the Massachusetts Institute of Technology Dept. of Mathematics and was supported by a NSF Graduate Fellowship and by Air Force grant OSR-82-0326.     

Bounding Betti numbers of bipartite graph ideals

We prove a conjectured lower bound of Nagel and Reiner on Betti numbers of edge ideals of bipartite graphs.     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

Walks and regular integral graphs

We establish a useful correspondence between the closed walks in regular graphs and the walks in infinite regular trees, which, after counting the walks of a given length between vertices at a given distance in an infinite regular tree, provides a lower bound on the number of closed walks in regular graphs. This lower bound is then applied to reduce the number of the feasible spectra of the 4-regular bipartite integral graphs by more than a half.Next, we give the details of the exhaustive computer search on all 4-regular bipartite graphs with up to 24 vertices, which yields a total of 47 integral graphs.     

Non-Trivial t-Intersection in the Function Lattice

The function lattice, or generalized Boolean algebra, is the set of ℓ-tuples with the ith coordinate an integer between 0 and a bound n_i. Two ℓ-tuples t-intersect if they have at least t common nonzero coordinates. We prove a Hilton–Milner type theorem for systems of t-intersecting ℓ-tuples.Received September 29, 2004     

Intersections ofk-element sets

LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection of maximum size satisfies .2715k+o(k)≦≦log₂ |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument. Some open questions are posed. This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366. Supported in part by a NSF postdoctoral Fellowship.     

Distance paired domination numbers of graphs

In this paper, we study a generalization of the paired domination number. Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.     

Spectral bounds for the betweenness of a graph

In this paper we find spectral bounds (Laplacian matrix) for the vertex and the edge betweenness of a graph. We also relate the edge betweenness with the isoperimetric number and the edge forwarding and edge expansion indices of the graph allowing a new upper bound on its diameter. The results are of interest as they can be used in the study of communication properties of real networks, in particular for dynamical processes taking place on them (broadcasting, network synchronization, virus spreading, etc.).     

Estimates of MM type for the multivariate linear model

We propose a class of robust estimates for multivariate linear models. Based on the approach of MM-estimation (Yohai 1987, [24]), we estimate the regression coefficients and the covariance matrix of the errors simultaneously. These estimates have both a high breakdown point and high asymptotic efficiency under Gaussian errors. We prove consistency and asymptotic normality assuming errors with an elliptical distribution. We describe an iterative algorithm for the numerical calculation of these estimates. The advantages of the proposed estimates over their competitors are demonstrated through both simulated and real data.