1
$\begingroup$

I'm currently studying a paper which uses extensively the term 'min-max theorems' in graph theory, and claims to present a tool allowing to generalize these theorems. (here is the link to the paper if needed)

Among those, we can find for example :

  • The max-flow-min cut theorem.
  • Edmond's disjoint arborescences theorem (link).

I have some intuition about what a min-max theorem would be, but I can't come with a concise and precise definition.

My question is : what would be a definition of such a family of theorems ?

And a second question along : is this min-max theorem concept always linked to the strong duality theorem, meaning that they mainly state that one problem is actually the dual of the other, like the max-flow-min-cut is ?

$\endgroup$
2
$\begingroup$

A min-max theorem is simply a theorem that says that the minimum value possible for one quantity is the maximum value possible for some other. For example,

  • Max-flow min-cut says that the value of the biggest flow between two vertices in a weighted graph is equal to the value of the minimum cut that separates them. Closely related, Menger's Theorem says that the maximum number of edge-disjoint paths between two vertex sets is equal to the size of the minimum cut that separates them.

  • Edmonds' Theorem says that the maximum number of edge-disjoint spanning arborescences is equal to the minimum value of something called $\varrho(X)$ over certain non-empty vertex sets.

  • The cops and robbers characterization of treewidth says that the minimum width over all tree decompositions is equal to the maximum number of cops that a robber can escape (er, plus or minus one, probably).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.