Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

Lower bounds on the minimum distance in Hermitian one-point differential codes

Korchmáros and Nagy [Hermitian codes from higher degree places. J Pure Appl Algebra, doi: 10. 1016/j.jpaa.2013.04.002, 2013] computed the Weierstrass gap sequence G(P) of the Hermitian function field Fq2( H ) at any place P of degree 3, and obtained an explicit formula of the Matthews-Michel lower bound on the minimum distance in the associated differential Hermitian code CΩ(D, mP ) where the divisor D is, as usual, the sum of all but one 1-degree Fq2-rational places of Fq2( H ) and m is a positive integer. For plenty of values of m depending on q, this provided improvements on the designed minimum distance of CΩ(D, mP). Further improvements from G(P) were obtained by Korchmáros and Nagy relying on algebraic geometry. Here slightly weaker improvements are obtained from G(P) with the usual function-field method depending on linear series, Riemann-Roch theorem and Weierstrass semigroups. We also survey the known results on this subject.     

Lower bounds for the chromatic numbers of distance graphs with large girth

We obtain some specific exponential lower bounds for the chromatic numbers of distance graphs with large girth.     

Upper bounds on geometric permutations for convex sets

LetA be a family ofn pairwise disjoint compact convex sets inR ^d. Let . We show that the directed lines inR ^d, d 3, can be partitioned into sets such that any two directed lines in the same set which intersect anyAA generate the same ordering onA. The directed lines inR ² can be partitioned into 12n such sets. This bounds the number of geometric permutations onA by 1/2 _d ford3 and by 6n ford=2.     

Lower bounds of Tian's invariant under toric invariances

On some toric Fano manifolds with metrics in the first Chern class, we show that a large family of smooth almost pluri-subharmonic functions (i.e. subharmonic with respect to the metric) with maximum equal to 0 admits a lower envelope. In our previous papers (A. Ben Abdesselem (2006) [4] and A. Ben Abdesselem and B. Dridi (2008) [5]) we established such envelopes when the functions considered are invariant under the action of a larger automorphisms group. Here we only consider the invariances due to the of the toric structure of the manifolds.     

Lower bounds for the size in four families of minimum broadcast graphs

In this paper, we give a lower bound for the size B(n) of a minimum broadcast graph of order n = 2^k − 4, 2^k − 6, 2^k − 5 or 2^k − 3 which is shown to be accurate in the cases when k = 5 and k = 6. This result provides, together with an upper bound obtained by a construction given in Bermond et al. (1992), an estimation of the value B(n) for n = 2^k − 4.     

Two new bounds on the size of binary codes with a minimum distance of three

We prove two new upper bounds on the size of binary codes with a minimum distance of three, namelyA(10, 3)76 andA(11, 3)152.     

Lower bounds on the number of scattering poles under lines parallel to the axis

We provide lower bounds in slab domains on the number of scattering poles, generated by two different types of periodic non-hyperbolic rays. For the first one all eigenvalues of the corresponding Poincaré map are equal to one and for the second one two of the eigenvalues are equal to one and two are different from one. In the second case we find also the closest to the real axis “line of poles”     

Lower bounds for the complexity of the graph of the Hausdorff distance as a function of transformation

The Hausdorff distance is a measure defined between two sets in some metric space. This paper investigates how the Hausdorff distance changes as one set is transformed by some transformation group. Algorithms to find the minimum distance as one set is transformed have been described, but few lower bounds are known. We consider the complexity of the graph of the Hausdorff distance as a function of transformation, and exhibit some constructions that give lower bounds for this complexity. We exhibit lower-bound constructions for both sets of points in the plane, and sets of points and line segments; we consider the graph of the directed Hausdorff distance under translation, rigid motion, translation and scaling, and affine transformation. Many of the results can also be extended to the undirected Hausdorff distance. These lower bounds are for the complexity of the graph of the Hausdorff distance, and thus do not necessarily bound algorithms that search this graph; however, they do give an indication of how complex the search may be. This work was supported in part by National Science Foundation PYI Grant IRI-9057928 and matching funds from General Electric, Kodak, and Xerox, and in part by Air Force Contract AFOSR-91-0328.     

Sharp bounds on the distance spectral radius and the distance energy of graphs

The D-eigenvalues {μ₁,μ₂,…,…,μ_p} of a graph G are the eigenvalues of its distance matrix D and form the D-spectrum of G denoted by spec_D(G). The greatest D-eigenvalue is called the D-spectral radius of G denoted by μ₁. The D-energy E_D(G) of the graph G is the sum of the absolute values of its D-eigenvalues. In this paper we obtain some lower bounds for μ₁ and characterize those graphs for which these bounds are best possible. We also obtain an upperbound for E_D(G) and determine those maximal D-energy graphs.     

Lower bounds on the cover-index of a graph

In this paper we give some new lower bounds for the cover-index of graphs with multiple edges permitted. The results are analogous to upper bounds for the chromatic index. We show that a simple graph with cover-index different from the minimum degree has at least three vertices of minimum degree. This implies that almost all simple graphs have cover-index equal to the minimum degree.     

Lower bounds on two-terminal network reliability

Computing the probability that two nodes in a probabilistic network are connected is a well-known computationally difficult problem. Two strategies are devised for obtaining lower bounds on the connection probability for two terminals. The first improves on the Kruskal-Katona bound by using efficient computations of small pathsets. The second strategy employs efficient algorithms for finding edge-disjoint paths. The resulting bounds are compared; while the edge-disjoint path bounds typically outperform the Kruskal-Katona bounds, they do not always do so. Finally, a method is outlined for developing a uniform bound which combines both strategies.