Frédéric Meunier
CERMICS, Ecole des Ponts



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

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


The open problems in the pdf format.





1. The 43-conjecture

A word a1,,a over the alphabet {-, +} is antipalindromic if ai = -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 43n that is antipalindromic.

To avoir any ambiguity, here is another formulation. Let w be denoted a1,a2,,a2n. If |{i = ai = +}| = n and |{i = ai = -}| = n, then the conjecture claims that there exist m integers i1,,im, with m 43n, such that i1 < ⋅⋅⋅ < im, and such that aik,aik+1,,aim,ai1,,ak-1 is antipalindromic for some integer k.

Note that it is easy to prove that the conjecture is true when we replace 43n 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

                     {     (   )              }
V (KGr (m, ℓ,s))  =    A ∈  [mℓ] : A is s-stable
      r                                         r
E (KG  (m, ℓ,s))  =  {{A1, ...,Ar } : Ai ∈ V (KG (m, ℓ,s)),Ai ∩ Aj =  ∅ for i ⁄= j}.

Conjecture 2. If m max(s,r)

                  ⌈                      ⌉
χ (KGr (m, ℓ,s)) =  m----max-(s,r)(ℓ --1-) .
                            r - 1

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 [112]: 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

∂ △q -1 = {F ⊆  [q] : F ⁄= [q]}.
The group Zq acts on q-1 by cyclically permuting their elements. This action extends naturally to the k-fold join of this complex.

Consider En-1Zq the n-fold join of Zq with itself, where Zq is seen as a 0-dimensional simplicial complex. Let λ : sd(En-1Zq) (q-1)*m be a Z q-equivariant simplicial map. If q is prime, the Zq-action is free on both sd(En-1Zq) 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-1Zq), i.e. m(q - 1) n. If q is not prime, the Zq-action is no longer free on (q-1)*m, while being still free on sd(En-1Zq). 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 Zq-equivariant simplicial map λ : sd(En-1Zq) (q-1)*m with n > m(q - 1)?

Another way to formulate the question is to ask whether (sd(En-1Zq), (WZq)m, Zqm) 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) Kfor 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 P (resp. P(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 (Ik) kK – the classes – modeling the players with same characteristics: they share a same collection of cost functions (cak : + +)aA, a same origin sk, and a same destination tk. A player in Ik is said to be of class k.

A strategy profile is a measurable mapping σ : I P such that σ(i) P(sk,tk) for all k K and all i Ik. We denote by x ak the number of class k players i such that a is in σ(i):

xka = λ {i ∈ Ik : a ∈ σ (i)}.
The vector xk = (x ak) aAk is an sk-tk flow of value λ(Ik): for each v V k \{sk,tk}, we have
  ∑          ∑
       xk =       xk
   +    a      -    a
a∈δ (v)     a∈δ (v)
and
  ∑      k    ∑      k     ∑     k     ∑     k       k
       x a -        xa =        xa -        xa = λ(I ).
a∈δ+(sk)     a∈δ-(sk)     a∈δ-(tk)     a∈δ+(tk)
The vector (xk) kK is thus a multiflow. The total number of players i such that a is in σ(i) is kKxak and is denoted xa. We denote by x the vector (xa)aA.

The cost of arc a for a class k player is cak(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 Ik we have

 ∑    k                ∑   k
     ca(xa) = P m∈iPnk k    ca(xa).
a∈σ(i)             (s ,t )a∈P

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. cak(x) = α akx + β ak with αak > 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.

References

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.