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

DOI10.1016/J.DISC.2016.05.025zbMATH Open1339.05194arXiv1408.3197OpenAlexW1555013930MaRDI QIDQ2629296FDOQ2629296

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)

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.

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

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

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)

Cites Work

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

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)