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

DOI10.1016/J.DISC.2016.05.025MaRDI QIDQ2629296zbMATH OpenOpenAlexFDO

Authors G. Araujo-Pardo, Juan Carlos Díaz-Patiño, L. Montejano, Deborah Oliveros

Publication date 5 July 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.3197

zbMATH Keywords

extremal graph theoryfractional chromatic numberKneser hypergraphs\((p, q)\)-propertyErdős-Ko-Rado

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: 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 emph{$(p,q)$-extremal problem} consists in finding the maximum number of edges on a $k$-uniform hypergraph $mathcalH$ with $n$ vertices such that among any $p$ edges some $q$ of them have no empty intersection. In this paper we have found a link between the fractional chromatic number of Kneser hypergraphs and the $(p,q)$-extremal problem and also solve the $(p,q)$-extremal problem for graphs if $n$ is sufficiently large and $pgeqqgeq3$ by proposing it as a problem of extremal graph theory. With the aid of this result we calculate the fractional chromatic number of Kneser hypergraphs when they are composed with sets of cardinality 2.

Recommendations

• On the chromatic number of generalized Kneser hypergraphs
• Coloring hypercomplete and hyperpath graphs
• The chromatic number of almost stable Kneser hypergraphs
• Hypergraphs with many Kneser colorings
• On the chromatic number of general Kneser hypergraphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• scientific article; zbMATH DE number 2209723 (Why is no real title available?)
• A generalized Kneser conjecture
• Algorithmic graph theory and perfect graphs
• Arc coverings of graphs
• Hypergraph Turán numbers of linear cycles
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Improved bounds for Erdős' matching conjecture
• Kneser's conjecture, chromatic number, and homotopy
• On Erdős' extremal problem on matchings in hypergraphs
• On Sperner families satisfying an additional condition
• On maximal paths and circuits of graphs
• On the maximum number of edges in a hypergraph with given matching number
• On the maximum number of edges in a triple system not containing a disjoint family of a given size
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• The size of a hypergraph and its matching number
• Über eine Variante zum Hellyschen Satz

Cited in

(2)

• Coloring hypergraphs with excluded minors
• Coloring hypercomplete and hyperpath graphs

This page was built for publication: The \((p, q)\)-extremal problem and the fractional chromatic number of Kneser hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2629296)