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 of redundant multicast routing problem with SRLG-diverse constraints: edge,path and tree models

This paper proposes three classes of alternative mathematical programming models (i.e., edge-based, path-based, and tree-based) for redundant multicast routing problem with shared risk link group (SRLG)-diverse constraints (RMR-SRLGD). The goal of RMR-SRLGD problem is to find two redundant multicast trees, each from one of the two sources to every destination, at a minimum cost while ensuring the paths from the two sources to a destination do not share any common risks. Such risk could cause the failures of multiple links simultaneously. Therefore, the RMR-SRLGD problem ensures the availability and reliability of multicast services. We investigated and compared the theoretical bounds of the linear programming (LP) relaxation for all models. We also summarized a hierarchy relationship of the tightness of LP bounds for the proposed models.     

Bounds on graph spectra

The largest eigenvalue of the adjacency matrix of a graph has received considerable attention in the literature. Not nearly as much seems to be known about bounds on other eigenvalues of the spectrum. Several results are presented here toward that goal, first for the general class of simple graphs, then for triangle-free graphs and finally for the even more restricted class of bipartite graphs.     

Bounds on affine caps

We present a short and elementary proof for an upper bound on caps in affine spaces. The bound generalizes and strengthens a result by Meshulam. The proof is inspired by Meshulam's Fourier transform method without making explicit use of the Fourier transform. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 111–115, 2002; DOI 10.1002/jcd.10000     

Bounds on a polynomial

Methods are given for isolating and approximating the maxima, minima, and real roots of a polynomial with real coefficients. The methods are based on a variation diminishing property of the Bernstein coefficients of the polynomial and use of a recursive bisection technique.     

Spectral Bounds on Orbifold Isotropy

We first show that a Laplace isospectral family of Riemannian orbifolds, satisfying a lower Ricci curvature bound, contains orbifolds with points of only finitely many isotropy types. If we restrict our attention to orbifolds with only isolated singularities, and assume a lower sectional curvature bound, then the number of singular points in an orbifold in such an isospectral family is universally bounded above. These proofs employ spectral theory methods of Brooks, Perry and Petersen, as well as comparison geometry techniques developed by Grove and Petersen.This research was partially supported by NSF grant DMS 0072534.     

New Bounds on Crossing Numbers

The crossing number , cr(G) , of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n,e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos os and Guy by showing that κ(n,e)n ² /e ³ tends to a positive constant as n→∈fty and n l e l n ² . Similar results hold for graph drawings on any other surface of fixed genus. We prove better bounds for graphs satisfying some monotone properties. In particular, we show that if G is a graph with n vertices and e≥ 4n edges, which does not contain a cycle of length four (resp. six ), then its crossing number is at least ce ⁴ /n ³ (resp. ce ⁵ /n ⁴ ), where c>0 is a suitable constant. These results cannot be improved, apart from the value of the constant. This settles a question of Simonovits. Received January 27, 1999, and in revised form March 23, 1999.     

Bounds on distances between eigenvalues

Explicit (computable) lower and upper bounds on the distances between a given real eigenvalue of a real square matrix and the remaining (not necessarily real) eigenvalues of the matrix are developed.     

Exact Bounds on Cross-Intersecting Families

 Let ?, ℬ be cross-intersecting families, where ? is a k-uniform, ℬ is an l-uniform family on a finite underlying set. A tight bound is given on |?|+|ℬ|, if c≤|?|≤d holds for some natural numbers c,d. Received: February 8, 1999 Final version received: May 17, 2000     

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.     

Theorems on matroid connectivity

It is proved that for every k?4 there is a Δ(k) such that for every g there is a graph G with maximal degree at most Δ(k), chromatic number at least k and girth at least g. In fact, for a fixed k, the restriction of the maximal degree to Δ(k) does not seem to slow down the growth of the maximal girth of a k-chromatic graph of order n as n → ∞.     

More Bounds on Norms of Generalized Characters with Applications to p-Local Bounds and Blocks

A new inequality concerning generalized characters of p-groupsis obtained and applications to bounding the number of irreduciblecharacters in blocks of finite groups are given. 2000 MathematicsSubject Classification 20C20.     

Sub-Laplacian Eigenvalue Bounds on CR Manifolds

We prove upper bounds for sub-Laplacian eigenvalues independent of a pseudo-Hermitian structure on a CR manifold. These bounds are compatible with the Menikoff-Sjöstrand asymptotic law, and can be viewed as a CR version of Korevaar's bounds for Laplace eigenvalues of conformal metrics.     

Bounds on leaves of one-dimensional foliations

Let X be a variety over an algebraically closed field, a onedimensional singular foliation, and a projective leaf of . We prove that