Longest cycles in 3-connected hypergraphs and bipartite graphs

Alexandr Kostochka; Mikhail Lavrov; Ruth Luo; Dara Zirlin

doi:10.1002/jgt.22762

Longest cycles in 3-connected hypergraphs and bipartite graphs

Alexandr Kostochka, Mikhail Lavrov, Ruth Luo, Dara Zirlin

Mathematics

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

Abstract

In the language of hypergraphs, our main result is a Dirac-type bound: We prove that every 3-connected hypergraph (Formula presented.) with (Formula presented.) has a hamiltonian Berge cycle. This is sharp and refines a conjecture by Jackson from 1981 (in the language of bipartite graphs). Our proofs are in the language of bipartite graphs, since the incidence graph of each hypergraph is bipartite.

Original language	English (US)
Pages (from-to)	758-782
Number of pages	25
Journal	Journal of Graph Theory
Volume	99
Issue number	4
DOIs	https://doi.org/10.1002/jgt.22762
State	Published - Apr 2022

Keywords

degree conditions
longest cycles
pancyclic hypergraphs

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Online availability

10.1002/jgt.22762

Library availability

Discover UIUC Full Text

Cite this

@article{b83c36d023924d659e50757f27b74b56,

title = "Longest cycles in 3-connected hypergraphs and bipartite graphs",

abstract = "In the language of hypergraphs, our main result is a Dirac-type bound: We prove that every 3-connected hypergraph (Formula presented.) with (Formula presented.) has a hamiltonian Berge cycle. This is sharp and refines a conjecture by Jackson from 1981 (in the language of bipartite graphs). Our proofs are in the language of bipartite graphs, since the incidence graph of each hypergraph is bipartite.",

keywords = "degree conditions, longest cycles, pancyclic hypergraphs",

author = "Alexandr Kostochka and Mikhail Lavrov and Ruth Luo and Dara Zirlin",

note = "Funding Information: We thank the referees for their helpful comments. Alexandr Kostochka research was supported in part by NSF Grant DMS‐1600592, NSF RTG Grant DMS‐1937241, and Grants 18‐01‐00353A and 19‐01‐00682 of the Russian Foundation for Basic Research. Ruth Luo research was supported in part by NSF Grants DMS‐1600592 and DMS‐1902808. Dara Zirlin research was supported in part by Arnold O. Beckman Research Award (UIUC) RB20003 and by NSF RTG Grant DMS‐1937241. Publisher Copyright: {\textcopyright} 2021 Wiley Periodicals LLC",

year = "2022",

month = apr,

doi = "10.1002/jgt.22762",

language = "English (US)",

volume = "99",

pages = "758--782",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Longest cycles in 3-connected hypergraphs and bipartite graphs

AU - Kostochka, Alexandr

AU - Lavrov, Mikhail

AU - Luo, Ruth

AU - Zirlin, Dara

N1 - Funding Information: We thank the referees for their helpful comments. Alexandr Kostochka research was supported in part by NSF Grant DMS‐1600592, NSF RTG Grant DMS‐1937241, and Grants 18‐01‐00353A and 19‐01‐00682 of the Russian Foundation for Basic Research. Ruth Luo research was supported in part by NSF Grants DMS‐1600592 and DMS‐1902808. Dara Zirlin research was supported in part by Arnold O. Beckman Research Award (UIUC) RB20003 and by NSF RTG Grant DMS‐1937241. Publisher Copyright: © 2021 Wiley Periodicals LLC

PY - 2022/4

Y1 - 2022/4

N2 - In the language of hypergraphs, our main result is a Dirac-type bound: We prove that every 3-connected hypergraph (Formula presented.) with (Formula presented.) has a hamiltonian Berge cycle. This is sharp and refines a conjecture by Jackson from 1981 (in the language of bipartite graphs). Our proofs are in the language of bipartite graphs, since the incidence graph of each hypergraph is bipartite.

AB - In the language of hypergraphs, our main result is a Dirac-type bound: We prove that every 3-connected hypergraph (Formula presented.) with (Formula presented.) has a hamiltonian Berge cycle. This is sharp and refines a conjecture by Jackson from 1981 (in the language of bipartite graphs). Our proofs are in the language of bipartite graphs, since the incidence graph of each hypergraph is bipartite.

KW - degree conditions

KW - longest cycles

KW - pancyclic hypergraphs

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

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

U2 - 10.1002/jgt.22762

DO - 10.1002/jgt.22762

M3 - Article

AN - SCOPUS:85117596893

SN - 0364-9024

VL - 99

SP - 758

EP - 782

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

Longest cycles in 3-connected hypergraphs and bipartite graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this