Common terminology used for lower/upper bounds

Question

Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it were an optimization problem then I would call it the optimal value or the optimal bound. Do you agree?

I am familiar with the term tight lower/upper bound. According to Wikipedia,

An upper bound is said to be a tight upper bound, a least upper bound, or a supremum if no smaller value is an upper bound. Similarly a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum if no greater value is a lower bound.

This definition does not mention whether the bound is achieved by an infinite family of instances or all instances. I looked up several books on "combinatorics", "algorithms", "graph theory" and "optimization". I could not find a reference that formally defines what a tight bound is.

According to the book Approximation Algorithms by Vijay V. Vazirani:

An infinite family of instances of this kind, showing that the analysis of an approximation algorithm is tight, will be referred to as a tight example.

So given a bound (e.g., upper bound), an example is tight if it represents an infinite family of instances achieving the bound. However, this bound may not be the best possible bound that can be found for the problem. What if you have the best possible bound (say optimal bound) for the problem and give a tight example corresponding to it? Although the example is still tight (by definition), it is different from other tight examples since its corresponding bound is optimal. So basically the question is, can we call the bound optimal (as I did!) or there is already a definition for such a bound? I have also heard of the phrase "theoretical lower/upper bound" but have no idea when we should use it!

How do you differentiate the above terminologies (preferably by formal definitions)? Are there any other terminologies that are not mentioned here?

Answer 1

The term “tight” has multiple uses, as is mentioned in a comment. However, you seem to be interested in a combinatorial context or on a combinatorial-type problem so I’m going to assume that contexts. Let’s say we are talking about a function, $f(n)$, that bounds $g(n)$. In your case, $g$ is the true number of vertices of the $n^{th}$ graph in your family and $f$ is your bound.

$f$ is a tight bound for $g$ if there exists an $n$ such that $g(n)=f(n)$.

Notice that $f$ can be tight but still improvable. If you have that $g(n)=n-\epsilon\sin((n-1)/100)$ then $f(n)=n^2$ is a tight bound. It is an upper bound for $g$ and they agree for $n=1$. However, that doesn’t mean it cannot be improved. A better bound might be $f_k(n)=n^{1+k^{-1}}$. This family has the property that $g(n)<f_k(n)<f(n)$ for $n>1$ and $g(1)=f_k(1)+f(1)$.

I am generally not a fan of the term “optimal bound” because it’s usually inaccurate. The optimal bound for a sequence of integers is simply that sequence of integers, so if you have an “optimal bound” you almost always have an expression for the underlying process.

There are contexts in which the previous paragraphs is wrong, however, and you seem to think that you’ve proven that you bound is the best possible. If that’s the case, there aren’t any caveats to that sentence, and what you’ve proven is indeed a bound rather than an expression for the number of vertices in the graph, then “optimal bound” or “best possible bound” is the terminology that I would recommend using.