Increasing paths in countable graphs
| Autor: | Bradley Elliott, Andrii Arman, Vojtěch Rödl |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Hypergraph
Property (philosophy) 010102 general mathematics 0102 computer and information sciences 01 natural sciences Graph Theoretical Computer Science Vertex (geometry) Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Simple (abstract algebra) Path (graph theory) FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Countable set Combinatorics (math.CO) 0101 mathematics Mathematics |
| Zdroj: | Journal of Combinatorial Theory, Series A. 183:105491 |
| ISSN: | 0097-3165 |
| DOI: | 10.1016/j.jcta.2021.105491 |
| Popis: | 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 $\mathbb{Z}$ (instead of $\mathbb{N}$). For example, we show that for every simple hypergraph, there is a labelling of its edges by $\mathbb{Z}$ that forbids one-way infinite increasing paths. Comment: 27 pages, 3 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect