Tight paths in convex geometric hypergraphs

Zoltán Füredi; Tao Jiang; Alexandr Kostochka; Dhruv Mubayi; Jacques Verstraëte

doi:10.19086/aic.12044

Tight paths in convex geometric hypergraphs

Zoltán Füredi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraëte

Mathematics

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

Abstract

In this paper, we prove a theorem on tight paths in convex geometric hypergraphs, which is asymptotically sharp in infinitely many cases. Our geometric theorem is a common generalization of early results of Hopf and Pannwitz [12], Sutherland [19], Kupitz and Perles [16] for convex geometric graphs, as well as the classical Erdős-Gallai Theorem [6] for graphs. As a consequence, we obtain the first substantial improvement on the Turán problem for tight paths in uniform hypergraphs.

Original language	English (US)
Article number	1
Pages (from-to)	1-14
Number of pages	14
Journal	Advances in Combinatorics
Volume	2020
Issue number	1
DOIs	https://doi.org/10.19086/aic.12044
State	Published - 2020

Keywords

Convex geometric hypergraphs
Paths
Turan number

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Online availability

10.19086/aic.12044License: CC BY

Library availability

Discover UIUC Full Text

Cite this

@article{bfc99017371d45b48700beaa88ca66b3,

title = "Tight paths in convex geometric hypergraphs",

abstract = "In this paper, we prove a theorem on tight paths in convex geometric hypergraphs, which is asymptotically sharp in infinitely many cases. Our geometric theorem is a common generalization of early results of Hopf and Pannwitz [12], Sutherland [19], Kupitz and Perles [16] for convex geometric graphs, as well as the classical Erd{\H o}s-Gallai Theorem [6] for graphs. As a consequence, we obtain the first substantial improvement on the Tur{\'a}n problem for tight paths in uniform hypergraphs.",

keywords = "Convex geometric hypergraphs, Paths, Turan number",

author = "Zolt{\'a}n F{\"u}redi and Tao Jiang and Alexandr Kostochka and Dhruv Mubayi and Jacques Verstra{\"e}te",

note = "Funding Information: ∗Supported by grant K116769 from the National Research, Development and Innovation Office NKFIH and by the Simons Foundation Collaboration grant 317487. †Supported by National Science Foundation award DMS-1400249. ‡Supported by NSF grant DMS1600592, by Arnold O. Beckman Award RB20003 of the University of Illinois at Urbana-Champaign and by grants 18-01-00353A and 19-01-00682 of the Russian Foundation for Basic Research. §Supported by NSF grants DMS-1300138 and DMS-1763317. ¶Supported by NSF grants DMS-1556524 and DMS-1800332.",

year = "2020",

doi = "10.19086/aic.12044",

language = "English (US)",

volume = "2020",

pages = "1--14",

journal = "Advances in Combinatorics",

issn = "2517-5599",

publisher = "Alliance of Diamond Open Access Journals",

number = "1",

}

TY - JOUR

T1 - Tight paths in convex geometric hypergraphs

AU - Füredi, Zoltán

AU - Jiang, Tao

AU - Kostochka, Alexandr

AU - Mubayi, Dhruv

AU - Verstraëte, Jacques

N1 - Funding Information: ∗Supported by grant K116769 from the National Research, Development and Innovation Office NKFIH and by the Simons Foundation Collaboration grant 317487. †Supported by National Science Foundation award DMS-1400249. ‡Supported by NSF grant DMS1600592, by Arnold O. Beckman Award RB20003 of the University of Illinois at Urbana-Champaign and by grants 18-01-00353A and 19-01-00682 of the Russian Foundation for Basic Research. §Supported by NSF grants DMS-1300138 and DMS-1763317. ¶Supported by NSF grants DMS-1556524 and DMS-1800332.

PY - 2020

Y1 - 2020

N2 - In this paper, we prove a theorem on tight paths in convex geometric hypergraphs, which is asymptotically sharp in infinitely many cases. Our geometric theorem is a common generalization of early results of Hopf and Pannwitz [12], Sutherland [19], Kupitz and Perles [16] for convex geometric graphs, as well as the classical Erdős-Gallai Theorem [6] for graphs. As a consequence, we obtain the first substantial improvement on the Turán problem for tight paths in uniform hypergraphs.

AB - In this paper, we prove a theorem on tight paths in convex geometric hypergraphs, which is asymptotically sharp in infinitely many cases. Our geometric theorem is a common generalization of early results of Hopf and Pannwitz [12], Sutherland [19], Kupitz and Perles [16] for convex geometric graphs, as well as the classical Erdős-Gallai Theorem [6] for graphs. As a consequence, we obtain the first substantial improvement on the Turán problem for tight paths in uniform hypergraphs.

KW - Convex geometric hypergraphs

KW - Paths

KW - Turan number

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

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

U2 - 10.19086/aic.12044

DO - 10.19086/aic.12044

M3 - Article

SN - 2517-5599

VL - 2020

SP - 1

EP - 14

JO - Advances in Combinatorics

JF - Advances in Combinatorics

IS - 1

M1 - 1

ER -

Tight paths in convex geometric hypergraphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this