Two-regular subgraphs of odd-uniform hypergraphs

Jie Han; Jaehoon Kim

doi:10.1016/j.jctb.2017.08.009

Two-regular subgraphs of odd-uniform hypergraphs

Jie Han, Jaehoon Kim

University of Birmingham

科研成果: 期刊稿件 › 文章 › 同行评审

3 引用（Scopus）

摘要

Let k≥3 be an odd integer and let n be a sufficiently large integer. We prove that the maximum number of edges in an n-vertex k-uniform hypergraph containing no 2-regular subgraphs is (n−1k−1)+⌊[Formula presented]⌋, and the equality holds if and only if H is a full k-star with center v together with a maximal matching omitting v. This verifies a conjecture of Mubayi and Verstraëte.

源语言	英语
页（从-至）	175-191
页数	17
期刊	Journal of Combinatorial Theory. Series B
卷	128
DOI	https://doi.org/10.1016/j.jctb.2017.08.009
出版状态	已出版 - 1月 2018
已对外发布	是

访问文件

10.1016/j.jctb.2017.08.009

其它文件与链接

链接到 Scopus 的出版物

引用此

Han, J., & Kim, J. (2018). Two-regular subgraphs of odd-uniform hypergraphs. Journal of Combinatorial Theory. Series B, 128, 175-191. https://doi.org/10.1016/j.jctb.2017.08.009

@article{24a3188a122542f483cd2b539c33077f,

title = "Two-regular subgraphs of odd-uniform hypergraphs",

abstract = "Let k≥3 be an odd integer and let n be a sufficiently large integer. We prove that the maximum number of edges in an n-vertex k-uniform hypergraph containing no 2-regular subgraphs is (n−1k−1)+⌊[Formula presented]⌋, and the equality holds if and only if H is a full k-star with center v together with a maximal matching omitting v. This verifies a conjecture of Mubayi and Verstra{\"e}te.",

keywords = "Hypergraph, Regular graph, Regular subgraph, Subgraph",

author = "Jie Han and Jaehoon Kim",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2018",

month = jan,

doi = "10.1016/j.jctb.2017.08.009",

language = "English",

volume = "128",

pages = "175--191",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Two-regular subgraphs of odd-uniform hypergraphs

AU - Han, Jie

AU - Kim, Jaehoon

PY - 2018/1

Y1 - 2018/1

N2 - Let k≥3 be an odd integer and let n be a sufficiently large integer. We prove that the maximum number of edges in an n-vertex k-uniform hypergraph containing no 2-regular subgraphs is (n−1k−1)+⌊[Formula presented]⌋, and the equality holds if and only if H is a full k-star with center v together with a maximal matching omitting v. This verifies a conjecture of Mubayi and Verstraëte.

AB - Let k≥3 be an odd integer and let n be a sufficiently large integer. We prove that the maximum number of edges in an n-vertex k-uniform hypergraph containing no 2-regular subgraphs is (n−1k−1)+⌊[Formula presented]⌋, and the equality holds if and only if H is a full k-star with center v together with a maximal matching omitting v. This verifies a conjecture of Mubayi and Verstraëte.

KW - Hypergraph

KW - Regular graph

KW - Regular subgraph

KW - Subgraph

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

U2 - 10.1016/j.jctb.2017.08.009

DO - 10.1016/j.jctb.2017.08.009

M3 - Article

AN - SCOPUS:85029215621

SN - 0095-8956

VL - 128

SP - 175

EP - 191

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Two-regular subgraphs of odd-uniform hypergraphs

摘要

访问文件

其它文件与链接

指纹

引用此