Increasing paths in countable graphs

DOI10.1016/J.JCTA.2021.105491MaRDI QIDQ2040501zbMATH OpenOpenAlexFDO

Authors Andrii Arman, Bradley Elliott, Vojtěch Rödl

Publication date 14 July 2021

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

countable graphsincreasing paths in graphsincreasing paths in hypergraphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: In this paper we study variations of an old result by M"{u}ller, Reiterman, and the last author stating that a countable graph has a subgraph with infinite degrees if and only if in any labeling of the vertices (or edges) of this graph by positive integers we can always find an infinite increasing path. We study corresponding questions for hypergraphs and directed graphs. For example we show that the condition that a hypergraph contains a subhypergraph with infinite degrees is equivalent to the condition that any vertex labeling contains an infinite increasing loose path. We also find an equivalent condition for a graph to have a property that any vertex labeling with positive integers contains a path of arbitrary finite length, and we study related problems for oriented graphs and labelings with $mathbbZ$ (instead of $mathbbN$). For example, we show that for every simple hypergraph, there is a labelling of its edges by $mathbbZ$ that forbids one-way infinite increasing paths.

Recommendations

• Counting paths in graphs
• Increasing paths in edge-ordered graphs: the hypercube and random graph
• On the number of increasing paths in labeled cycles and stars
• Counting paths in digraphs
• Increasing paths in regular trees
• scientific article; zbMATH DE number 3877220
• Approximately counting paths and cycles in a graph
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• On the order of countable graphs
• scientific article; zbMATH DE number 2152547

Cites work

• A note on monotone paths in labeled graphs
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• Increasing paths in edge ordered graphs
• Monotone paths in dense edge-ordered graphs
• Monotone paths in ordered graphs
• Nearly-linear monotone paths in edge-ordered graphs
• Nombre chromatique et plus longs chemins d'un graphe

Cited in

(3)

• Counting paths in graphs
• On the number of increasing paths in labeled cycles and stars
• scientific article; zbMATH DE number 5585075 (Why is no real title available?)

This page was built for publication: Increasing paths in countable graphs

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