A path Turán problem for infinite graphs

DOI10.1016/J.DISC.2016.08.019MaRDI QIDQ2374174zbMATH OpenOpenAlexFDO

Authors Xing Peng, Craig Timmons

Publication date 14 December 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.06371

zbMATH Keywords

infinite graphs path Turán

Mathematics Subject Classification ID

Paths and cycles (05C38) Infinite graphs (05C63)

Abstract: Let

G

be an infinite graph whose vertex set is the set of positive integers, and let

G_{n}

be the subgraph of

G

induced by the vertices

1, 2, d o t s, n

. An increasing path of length

k

in

G

, denoted

I_{k}

, is a sequence of

k + 1

vertices

1 l e q i_{1} < i_{2} < d o t s < i_{k + 1}

such that

i_{1}, i_{2}, l d o t s, i_{k + 1}

is a path in

G

. For

k g e q 2

, let

p (k)

be the supremum of

l i m i n f_{n i g h t a r r o w i n f t y} f r a c e (G_{n}) n^{2}

over all

I_{k}

-free graphs

G

. In 1962, Czipszer, ErdH{o}s, and Hajnal proved that

p (k) = f r a c 14 (1 - f r a c 1 k)

for

k i n 2, 3

. ErdH{o}s conjectured that this holds for all

k g e q 4

. This was disproved for certain values of

k

by Dudek and R"{o}dl who showed that

p (16) > f r a c 14 (1 - f r a c 116)

and

p (k) > f r a c 14 + f r a c 1200

for all

k g e q 162

. Given that the conjecture of ErdH{o}s is true for

k i n 2, 3

but false for large

k

, it is natural to ask for the smallest value of

k

for which

p (k) > f r a c 14 (1 - f r a c 1 k)

. In particular, the question of whether or not

p (4) = f r a c 14 (1 - f r a c 14)

was mentioned by Dudek and R"{o}dl as an open problem. We solve this problem by proving that

p (4) g e q f r a c 14 (1 - f r a c 14) + f r a c 1584064

and

p (k) > f r a c 14 (1 - f r a c 1 k)

for

4 l e q k l e q 15

. We also show that

p (4) l e q f r a c 14

which improves upon the previously best known upper bound on

p (4)

. Therefore,

p (4)

must lie somewhere between

f r a c 316 + f r a c 1584064

and

f r a c 14

Recommendations

Cites work

Cited in

(5)

Describes a project that uses

Uses Software

Mathematica

This page was built for publication: A path Turán problem for infinite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2374174)