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?