Maximum hypergraphs without regular subgraphs

Jaehoon Kim; Alexandr V. Kostochka

doi:10.7151/dmgt.1722

Maximum hypergraphs without regular subgraphs

Jaehoon Kim, Alexandr V. Kostochka

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2^n-1+r-2edges. 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, 2^n-1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n < r cannot be weakened.

Original language	English (US)
Pages (from-to)	151-166
Number of pages	16
Journal	Discussiones Mathematicae - Graph Theory
Volume	34
Issue number	1
DOIs	https://doi.org/10.7151/dmgt.1722
State	Published - 2014

Keywords

Hypergraphs
Regular graph
Set system
Subgraph

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.7151/dmgt.1722

Library availability

Discover UIUC Full Text

Cite this

@article{9b06a04013044cfa908e3cf968bf3c20,

title = "Maximum hypergraphs without regular subgraphs",

abstract = "We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n-1+r-2edges. 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.",

keywords = "Hypergraphs, Regular graph, Set system, Subgraph",

author = "Jaehoon Kim and Kostochka, {Alexandr V.}",

note = "Funding Information: 1Research of this author is partially supported by the Arnold O. Beckman Research Award of the University of Illinois at Urbana-Champaign. 2Research of this author is supported in part by NSF grant DMS-0965587 and by the Ministry of education and science of the Russian Federation (Contract no. 14.740.11.0868).",

year = "2014",

doi = "10.7151/dmgt.1722",

language = "English (US)",

volume = "34",

pages = "151--166",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "1",

}

TY - JOUR

T1 - Maximum hypergraphs without regular subgraphs

AU - Kim, Jaehoon

AU - Kostochka, Alexandr V.

N1 - Funding Information: 1Research of this author is partially supported by the Arnold O. Beckman Research Award of the University of Illinois at Urbana-Champaign. 2Research of this author is supported in part by NSF grant DMS-0965587 and by the Ministry of education and science of the Russian Federation (Contract no. 14.740.11.0868).

PY - 2014

Y1 - 2014

N2 - We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n-1+r-2edges. 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.

AB - We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n-1+r-2edges. 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.

KW - Hypergraphs

KW - Regular graph

KW - Set system

KW - Subgraph

UR - http://www.scopus.com/inward/record.url?scp=84892657451&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84892657451&partnerID=8YFLogxK

U2 - 10.7151/dmgt.1722

DO - 10.7151/dmgt.1722

M3 - Article

AN - SCOPUS:84892657451

SN - 1234-3099

VL - 34

SP - 151

EP - 166

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 1

ER -

Maximum hypergraphs without regular subgraphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this