CERMICS, Ecole des Ponts

I state here some open problems I have been interested in.

- The 4∕3-conjecture
- Chromatic number of stable Kneser hypergraphs
- Combinatorial Dold’s theorem with non-free actions
- Kernels in clique-acyclic orientations of perfect graphs
- Nash equilibria for nonatomic multiclass network congestion games

The open problems in the pdf format.

A word a_{1},…,a_{ℓ} over the alphabet {-, +} is antipalindromic if a_{i} = -a_{ℓ+1-i} for every i ∈ [ℓ]. The
following conjecture is due to Lyngsř and Pedersen [9].

Conjecture 1. Consider a circular word w over the alphabet {-, +} with n ‘-’ and n ‘+’. Then w has a linear subword of length at least 4∕3n that is antipalindromic.

To avoir any ambiguity, here is another formulation. Let w be denoted a_{1},a_{2},…,a_{2n}. If
|{i = a_{i} = +}| = n and |{i = a_{i} = -}| = n, then the conjecture claims that there exist m integers
i_{1},…,i_{m}, with m ≥ 4∕3n, such that i_{1} < < i_{m}, and such that a_{ik},a_{ik+1},…,a_{im},a_{i1},…,a_{k-1} is
antipalindromic for some integer k.

Note that it is easy to prove that the conjecture is true when we replace 4∕3n by n + α, for some
small integer α. It is also easy (polynomial) to compute the longest antipalindromic linear subword
of a circular word over the alphabet {-, +}.

2. The chromatic number of stable Kneser hypergraphs

A subset A of [m] is s-stable if s ≤|u - v|≤ m - s for any distinct u and v taken in
A. The s-stable r-uniform Kneser hypergraph KG ^{r}(m,ℓ,s) is the hypergraph defined
by

This conjecture, stated in [10], is known to be true for s = 1, since in this case, it simply provides the chromatic number of usual Kneser hypergraphs [2].

The case s = r is the Alon-Drewnowski-Łuczak-Ziegler conjecture [1, 12]: it states that the chromatic number of a Kneser hypergraphs of rank r does not change when we restrict its vertex set to the r-stable ℓ-subsets of [m]. It has been proved for r a power of 2, see [1],

The case r = 2 and s even has recently been proved by Chen [6].

3. Combinatorial Dold’s theorem with non-free actions

Let ∂△^{q-1} be the boundary of the standard (q - 1)-simplex seen as a simplicial complex. In
other words

Consider E_{n-1}Z_{q} the n-fold join of Z_{q} with itself, where Z_{q} is seen as a 0-dimensional simplicial
complex. Let λ : sd(E_{n-1}Z_{q}) → (∂△^{q-1})^{*m} be a Z_{
q}-equivariant simplicial map. If q is prime,
the Z_{q}-action is free on both sd(E_{n-1}Z_{q}) and (∂△^{q-1})^{*m}. Dold’s theorem ensures then
that the dimension of (∂△^{q-1})^{*m} is larger than the connectivity of sd(E_{
n-1}Z_{q}), i.e.
m(q - 1) ≥ n. If q is not prime, the Z_{q}-action is no longer free on (∂△^{q-1})^{*m}, while
being still free on sd(E_{n-1}Z_{q}). Dold’s theorem does not hold in full generality when the
free assumption is removed: counterexamples are known. But what about this special
case?

Question 3. For each nonprime q, do there exist integers m and n, and a Z_{q}-equivariant
simplicial map λ : sd(E_{n-1}Z_{q}) → (∂△^{q-1})^{*m} with n > m(q - 1)?

Another way to formulate the question is to ask whether (sd(E_{n-1}Z_{q}), (W_{Zq})^{m},♢_{
Zq}^{m}) has the
Tucker property when n > m(q - 1), in the terminology developed by Mark De Longueville and
Rade Živaljević, see [8].

4. Kernels in clique-acyclic orientations of perfect graphs

A kernel in a directed graph D = (V,A) is an independent subset K of the vertices such that we
have N^{+}(v) ∩ K≠∅ for any vertex v not in K. Not all directed graphs have a kernel and it is
NP-complete to decide whether a directed graph has a kernel [7]. A directed graph is clique-acyclic
if in every clique the subgraph of one-way arcs is acyclic. Boros and
Gurvich [5] proved that any clique-acyclic orientation of a perfect graph has a kernel (conjectured
by Berge and Duchet [4]).

Question 4. What is the complexity of computing a kernel in a clique-acyclic orientation of a perfect graph?

5. Computing Nash equilibria for nonatomic multiclass network congestion games

We are given a directed graph D = (V,A) modeling a transportation network. The set of all
paths (resp. s-t paths) is denoted by (resp. _{(s,t)}). The population of players is modeled as a
bounded real interval I endowed with the Lebesgue measure λ, the population measure. The set I
is partitioned into a finite number of measurable subsets (I^{k})_{
k∈K} – the classes – modeling
the players with same characteristics: they share a same collection of cost functions
(c_{a}^{k} : ℝ_{
+} → ℝ_{+})_{a∈A}, a same origin s^{k}, and a same destination t^{k}. A player in I^{k} is said to be of
class k.

A strategy profile is a measurable mapping σ : I → such that σ(i) ∈_{(sk,tk)} for all
k ∈ K and all i ∈ I^{k}. We denote by x_{
a}^{k} the number of class k players i such that a is in
σ(i):

The cost of arc a for a class k player is c_{a}^{k}(x_{
a}). For player, the cost of a path P is defined as the
sum of the costs of the arcs contained in P. Each player wants to select a minimum-cost
path.

A strategy profile is a (pure) Nash equilibrium if each path is only chosen by players for whom it
is a minimum-cost path. In other words, a strategy profile σ is a Nash equilibrium if for each class
k ∈ K and each player i ∈ I^{k} we have

A Nash equilibrium always exists in this framework [11].

Question 5. What is the complexity of computing a multiflow arising from a Nash
equilibrium when the cost functions are affine and increasing, i.e. c_{a}^{k}(x) = α_{
a}^{k}x + β_{
a}^{k} with
α_{a}^{k} > 0?

The problem is polynomial when there is only one class, i.e. |K| = 1. This is an easy consequence of the work by Beckmann [3]. It can also be proved that it is a polynomial problem when the number of classes and the number of vertices are fixed.

1. N. Alon, L. Drewnowski, and T Łuczak, Stable Kneser hypergraphs and ideals in ℕ with the Nikodým property, Proceedings of the American mathematical society 137 (2009), 467–471.

2. N. Alon, P. Frankl, and L. Lovász, The chromatic number of Kneser hypergraphs, Transactions Amer. Math. Soc. 298 (1986), 359–370.

3. M. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in economics of transportation, Yale University Press, New Haven, CT, 1956.

4. C. Berge and P. Duchet, “Séminaire MSH” (Paris), 1983.

5. E. Boros and V. Gurvich, Perfect graphs are kernel solvable, Discrete Mathematics 159 (1996), 35–55.

6. P.-A. Chen, On the multichromatic number of s-stable Kneser graphs, Journal of Graph Theory 79 (2015), 233–248.

7. V. Chvátal, Linear programming, W. H. Freeman; First Edition edition, 1983.

8. M. De Longueville and R.T. Živaljević, The Borsuk-Ulam property, Tucker property and constructive proofs in combinatorics, Journal of Combinatorial Theory Series A 113 (2006), 839–850.

9. R.B. Lyngsřand C.N.S. Pedersen, Protein folding in the 2d hp model, Tech. report, 1999.

10. F. Meunier, The chromatic number of almost stable Kneser hypergraphs, Journal of Combinatorial Theory Series A 118 (2011), 1820–1828.

11. D. Schmeidler, Equilibrium points on nonatomic games, J. Statist. Phys. 7 (1970), 295–300.

12. G. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), 671–691.