The (p, q)-extremal problem and the fractional chromatic number of Kneser hypergraphs

摘要

The problem of computing the chromatic number of Kneser hypergraphs has been extensively studied over the last 40 years and the fractional version of the chromatic number of Kneser hypergraphs is only solved for particular cases. The (p, q)-extremal problem is to maximize the number of edges in a k-uniform hypergraph H with given order subject to the constraint that any p edges contain q edges that have a vertex in common. In this paper we found a link between the fractional chromatic number of Kneser hypergraphs and the (p, q)-extremal problem. We solve the (p, q)-extremal problem for graphs and with the aid of this result we calculate the fractional chromatic number of Kneser hypergraphs when they are composed with sets of cardinality 2. (C) 2016 Elsevier B.V. Alt rights reserved.