Maximum Hypergraphs without Regular Subgraphs

Jaehoon Kim, and Alexandr V. Kostochka. "Maximum Hypergraphs without Regular Subgraphs." Discussiones Mathematicae Graph Theory 34.1 (2014): 151-166. <http://eudml.org/doc/268219>.

@article{JaehoonKim2014,
abstract = {We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n−1+r−2 edges. We conjecture that if n > r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, 2n−1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n > r cannot be weakened.},
author = {Jaehoon Kim, Alexandr V. Kostochka},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hypergraphs; set system; subgraph; regular graph},
language = {eng},
number = {1},
pages = {151-166},
title = {Maximum Hypergraphs without Regular Subgraphs},
url = {http://eudml.org/doc/268219},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Jaehoon Kim
AU - Alexandr V. Kostochka
TI - Maximum Hypergraphs without Regular Subgraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 1
SP - 151
EP - 166
AB - We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n−1+r−2 edges. We conjecture that if n > r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, 2n−1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n > r cannot be weakened.
LA - eng
KW - hypergraphs; set system; subgraph; regular graph
UR - http://eudml.org/doc/268219
ER -