Linking property
The term linking property usually refers to a property of the following type. Let [math]\mathcal{A}[/math] be a set of combinatorial objects, and let [math]\mathcal{B}[/math] be a set of conditions, where there is some notion of two conditions being compatible. The linking property is satisfied if for any two compatible conditions [math]B_1,B_2 \in \mathcal{B}[/math], at least one of the following holds:
- there exists [math]A \in \mathcal{A}[/math] satisfying both [math]B_1[/math] and [math]B_2[/math],
- there is no [math]A \in \mathcal{A}[/math] satisfying [math]B_1[/math],
- there is no [math]A \in \mathcal{A}[/math] satisfying [math]B_2[/math].
A classic example is the Mendelsohn-Dulmage theorem. Another example is the following result of Frank on k-arc-connected orientations of graphs.
Theorem [1]. Let G=(V,E) be an undirected graph, and let [math]f \leq g[/math] be two functions on V. If G has a k-arc-connected orientation with in-degree at least f(v) for every node v, and it has a k-arc-connected orientation with in-degree at most g(v) for every node v, then it has a k-arc-connected orientation where the in-degree of v is between f(v) and g(v) for every node v.
Linking property of integer polyhedra
An integer polyhedron [math]P \subseteq \mathbb{R}^n[/math] is said to satisfy the linking property if at least one of the following holds for any two n-dimensional integer vectors [math]f \leq g[/math]:
- P has an integer point x satisfying [math]f \leq x \leq g[/math],
- P has no integer point x satisfying [math]x \geq f[/math],
- P has no integer point x satisfying [math]x \leq g[/math].
The strong linking property is a stronger version where at least one of the following holds for any two n-dimensional integer vectors [math]f \leq g[/math] and any two integers [math]\alpha \leq \beta[/math]:
- P has an integer point x satisfying [math]f \leq x \leq g[/math] and [math]\alpha \leq \sum_{i=1}^n x_i \leq \beta[/math],
- P has no integer point x satisfying [math]x \geq f[/math] and [math]\sum_{i=1}^n x_i \leq \beta[/math],
- P has no integer point x satisfying [math]x \leq g[/math] and [math]\sum_{i=1}^n x_i \geq \alpha[/math].
It is shown in [2] that an integer polyhedron has the strong linking property if and only if it is a generalized polymatroid.
References
- ↑ A. Frank, On the orientation of graphs, J. Combinatorial Theory, Ser. B. , Vol. 28, 251-261, DOI link, author link
- ↑ T. Király, Base polyhedra and the linking property, EGRES Technical Report no. 2016-06
