An upper bound for a percolation constant

Résumé Dans cette note, nous étudions le temps minimum que prend un fluide pour se répandre à travers un milieu quand les temps nécessaires pour traverser les arcs du milieu sont des variables aléatoires indépendantes les unes des autres et tirées de la distribution uniforme et rectangulaire.     

An upper bound for the diameter of a polytope

The distance between two vertices of a polytope is the minimum number of edges in a path joining them. The diameter of a polytope is the greatest distance between two vertices of the polytope. We show that if P is a d-dimensional polytope with n facets, then the diameter of P is at most $\text{1}\text{3}\text{2}{}^{\mathrm{d?3}}\text{(n?d+}\text{5}\text{2}\text{)}$.     

An upper bound for Hilbert cubes

In this note we give a new upper bound for the largest size of subset of {1,2,…,n} not containing a k-cube.     

An upper bound for the k-domination number of a graph

The k-domination number of a graph G, γk(G), is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k, then γk(G) ≤ kp/(k + 1).     

An upper bound for the minimum rank of a graph

For a graph G of order n, the minimum rank of G is defined to be the smallest possible rank over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We prove an upper bound for minimum rank in terms of minimum degree of a vertex is valid for many graphs, including all bipartite graphs, and conjecture this bound is true over for all graphs, and prove a related bound for all zero-nonzero patterns of (not necessarily symmetric) matrices. Most of the results are valid for matrices over any infinite field, but need not be true for matrices over finite fields.     

An upper bound for the Waring rank of a form

Let \({\phi(n)}\) denote the Euler-totient function. We study the error term of the general k-th Riesz mean of the arithmetical function \({\frac {n}{\phi(n)}}\) for any positive integer \({k \ge 1}\) , namely the error term \({E_k(x)}\) where $${\frac{1}{k!} \sum_{n \leq x} \frac{n}{\phi(n)} \left(1-\frac{n}{x}\right)^k = M_k(x) + E_k(x).}$$ The upper bound for \({| E_k(x)|}\) established here thus improves the earlier known upper bounds for all integers \({k\geq 1}\) .     

An upper bound for the path number of a graph

The path number of a graph G, denoted p(G), is the minimum number of edge-disjoint paths covering the edges of G. Lovász has proved that if G has u odd vertices and g even vertices, then p(G) ≤ 1/2 u + g - 1 ≤ n - 1, where n is the total number of vertices of G. This paper clears up an error in Lovász's proof of the above result and uses an extension of his construction to show that p(G) ≤ 1/2 u + [3/4g] ≤ [3/4n].     

An upper bound for some ramsey numbers

New upper bounds for the ramsey numbers r(k, l) are obtained. In particular it is shown there is a constant A such that      

An upper bound for conforming Delaunay triangulations

A plane geometric graphC in ℝ² conforms to another such graphG if each edge ofG is the union of some edges ofC. It is proved that, for everyG withn vertices andm edges, there is a completion of a Delaunay triangulation ofO(m ² n) points that conforms toG. The algorithm that constructs the points is also described. Research of the first author is supported by the National Science Foundation under Grant CCR-8921421 and under the Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation. Work of the second author was conducted while he was on study leave at the University of Illinois.     

An upper bound for Cubicity in terms of Boxicity

An axis-parallel b-dimensional box is a Cartesian product R₁×R₂×?×R_b where each R_i (for 1≤i≤b) is a closed interval of the form [a_i,b_i] on the real line. The boxicity of any graph G, is the minimum positive integer b such that G can be represented as the intersection graph of axis-parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product R₁×R₂×?×R_b, where each R_i (for 1≤i≤b) is a closed interval of the form [a_i,a_i+1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by ). In this paper we prove that , where n is the number of vertices in the graph. We also show that this upper bound is tight.Some immediate consequences of the above result are listed below:

1.

Planar graphs have cubicity at most 3⌈log₂n⌉.

2.

Outer planar graphs have cubicity at most 2⌈log₂n⌉.

3.

Any graph of treewidth tw has cubicity at most (tw+2)⌈log₂n⌉. Thus, chordal graphs have cubicity at most (ω+1)⌈log₂n⌉ and circular arc graphs have cubicity at most (2ω+1)⌈log₂n⌉, where ω is the clique number.

The above upper bounds are tight, but for small constant factors.     

An upper bound for the zero-one knapsack problem and a branch and bound algorithm

A new way of computing the upper bound for the zero-one knapsack problem is presented, substantially improving on Dantzig's approach. A branch and bound algorithm is proposed, based on the above mentioned upper bound and on original backtracking and forward schemes. Extensive computational experiences indicate this new algorithm to be superior to the fastest algorithms known at present.     

An upper bound for permanents of nonnegative matrices

A recent conjecture of Caputo, Carlen, Lieb, and Loss, and, independently, of the author, states that the maximum of the permanent of a matrix whose rows are unit vectors in lp is attained either for the identity matrix I or for a constant multiple of the all-1 matrix J.The conjecture is known to be true for p=1 (I) and for p?2 (J).We prove the conjecture for a subinterval of (1,2), and show the conjectured upper bound to be true within a subexponential factor (in the dimension) for all 1<p<2. In fact, for p bounded away from 1, the conjectured upper bound is true within a constant factor.     

An upper bound for the number of matroids

An upper bound for the number of matroids is obtained. This upper bound complements the lower bound obtained by Piff and Welsh in [1].     

An upper bound for the first eigenvalue of a spherical cap

By working with suitable test functions, we obtain an upper bound for the principal eigenvalue of a geodesic ball on a sphere of arbitrary dimension. This bound is sharp in the limiting case when the radius of the ball approaches the diameter of the sphere.This research was supported by ARO Grant 28905-MA.     

An upper bound for the period length of a quadratic irrational

Using matrix representation of continued fractions we give an upper bound for the period length of a quadratic irrational which improves the result byPodsypanin.     

An upper bound for the harmonious chromatic number of a graph

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin.     

An upper bound for reflection length in Coxeter groups

Journal of Algebraic Combinatorics - We find an upper bound on the reflection or absolute length of Coxeter group elements as a function of the number of generators and the standard length. For any...     

An upper bound for the total chromatic number

The total chromatic number,(G), of a graphG, is defined to be the minimum number of colours needed to colour the vertices and edges of a graph in such a way that no adjacent vertices, no adjacent edges and no incident vertex and edge are given the same colour. This paper shows that , where(G) is the vertex chromatic number and(G) is the edge chromatic number of the graph.Partially supported by ORS grant ORS/84120