New Asymptotic Bounds on the Size of Multiple Packings of the Euclidean Sphere

Using lower bounds on components of the distance spectrum of a code on the Euclidean sphere obtained by linear programming, we derive new, better than known, upper bounds on the size of multiple packings of spherical caps on the surface of the sphere.     

Linear Programming Bounds for Codes of Small Size

Combining linear programming with the Plotkin–Johnson argument for constant weight codes, we derive upper bounds on the size of codes of lengthnand minimum distanced=(n − j) /2, 0<j<n^1/3.Forj=o(n^1/3)these bounds practically coincide with (are slightly better than) the Tietäväinen bound. Forjfixed and forjproportional ton^1/3, j<n^1/3-(2 /9)ln n,it improves on the earlier known results.     

Bounds on the Size of the Likelihood Ratio Test of Independence in a Contingency Table

Bounds are obtained on the limiting size of the nominal level-α likelihood ratio test of independence in a r × c contingency table. The situations considered include sampling with both marginal totals random and with one margin fixed. Upper and lower bounds are obtained. The limiting size is greater than α when some marginal probabilities are small. As the degrees of freedom increase, the limiting size tends to 1 for all α-values.     

Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph

In this paper we study tight lower bounds on the size of a maximum matching in a regular graph. For k ≥3, let G be a connected k-regular graph of order n and let α′(G) be the size of a maximum matching in G. We show that if k is even, then , while if k is odd, then . We show that both bounds are tight. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three

In this paper, we study lower bounds on the size of a maximum independent set and a maximum matching in a hypergraph of rank three. The rank in a hypergraph is the size of a maximum edge in the hypergraph. A hypergraph is simple if no two edges contain exactly the same vertices. Let H be a hypergraph and let and be the size of a maximum independent set and a maximum matching, respectively, in H, where a set of vertices in H is independent (also called strongly independent in the literature) if no two vertices in the set belong to a common edge. Let H be a hypergraph of rank at most three and maximum degree at most three. We show that with equality if and only if H is the Fano plane. In fact, we show that if H is connected and different from the Fano plane, then and we characterize the hypergraphs achieving equality in this bound. Using this result, we show that that if H is a simple connected 3‐uniform hypergraph of order at least 8 and with maximum degree at most three, then and there is a connected 3‐uniform hypergraph H of order 19 achieving this lower bound. Finally, we show that if H is a connected hypergraph of rank at most three that is not a complete hypergraph on vertices, where denotes the maximum degree in H, then and this bound is asymptotically best possible. © 2012 Wiley Periodicals, Inc. J. Graph Theory     

Lower Bounds for the Height and Size of the Ideal Class Group in CM-Fields

 We prove that, under the assumption of the Generalized Riemann Hypothesis, the exponent of the ideal class group of a CM-field goes to infinity with its absolute discriminant. This gives a positive answer to a question raised by Louboutin and Okazaki [4]. Received September 10, 2001; in revised form April 5, 2002     

Lower Bounds for the Height and Size of the Ideal Class Group in CM-Fields

 We prove that, under the assumption of the Generalized Riemann Hypothesis, the exponent of the ideal class group of a CM-field goes to infinity with its absolute discriminant. This gives a positive answer to a question raised by Louboutin and Okazaki [4].     

Lower Bounds of Size Ramsey Number for Graphs with Small Independence Number

Acta Mathematicae Applicatae Sinica, English Series - Let r ≥ 3 be an integer such that r ? 2 is a prime power and let H be a connected graph on n vertices with average degree at least...     

Bounds on the cover time

Consider a particle that moves on a connected, undirected graphG withn vertices. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. Tocover time is the first time when the particle has visited all the vertices in the graph starting from a given vertex. In this paper, we present upper and lower bounds that relate the expected cover time for a graph to the eigenvalues of the Markov chain that describes the random walk above. An interesting consequence is that regular expander graphs have expected cover time (n logn).This research was done while this author was a postdoctoral fellow in the Department of Computer Science, Princeton University, and it was supported in part by DNR grant N00014-87-K-0467.     

Bounds on the localization number

We consider the localization game played on graphs, wherein a set of cops attempt to determine the exact location of an invisible robber by exploiting distance probes. The corresponding optimization parameter for a graph G is called the localization number and is written as ζ(G). We settle a conjecture of Bosek et al by providing an upper bound on the chromatic number as a function of the localization number. In particular, we show that every graph with ζ(G) ≤ k has degeneracy less than 3^k and, consequently, satisfies χ(G) ≤ 3^ζ(G). We show further that this degeneracy bound is tight. We also prove that the localization number is at most 2 in outerplanar graphs, and we determine, up to an additive constant, the localization number of hypercubes.     

Bounds on the size of tetrahedralizations

This paper gives lower and upper bounds on the complexity of triangulating the region between polyhedra. Particular attention is given to the case of convex polyhedra and terrains. The first author was suported in part by NSF Grant CCR-90-02352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. The second author was supported in part by NSF Grant PHY-90-21984.     

Bounds on Malapportionment

Uniformly sized constituencies give voters similar influence on election outcomes. When constituencies are set up, seats are allocated to the administrative units, such as states or counties, using apportionment methods. According to the impossibility result of Balinski and Young, none of the methods satisfying basic monotonicity properties assign a rounded proportional number of seats (the Hare-quota). We study the malapportionment of constituencies and provide a simple bound as a function of the house size for an important class of divisor methods, a popular, monotonic family of techniques.     

Bounds on trees

We prove a finitary version of the Halpern–Läuchli Theorem. We also prove partition results about strong subtrees. Both results give estimates on the height of trees.     

关于Wallis不等式的上界和下界

利用Wallis公式对两个已知的不等式进行了改进,相应地,我们得到了两个更加精细的结果.     

Bounds on the moduli of polynomial zeros

In this paper, we develop methods for establishing improved bounds on the moduli of the zeros of complex and real polynomials. Specific (lacunary) as well as arbitrary polynomials are considered. The methods are applied to specific polynomials by way of example. Finally, we evaluate the quality of some bounds numerically.     

Bounds on the oscillation of spin system

A birth and death process is used to compare the dynamics of two finite Markov spin systems with different initial configurations. This procedure results in bounds on the oscillation of functionals of the finite spin system as a function of the initial configuration. Such bounds are used, in the one- and two-dimensional cases, to prove the existence of infinite Feller spin systems which do not satisfy T. Liggett's “bounded variation” condition on the interaction functions.