Tiling problems in edge-ordered graphs

EUROCOMB’23

Abstract
Given graphs $F$ and $G$, a perfect $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ that together cover all the vertices in $G$. The study of the minimum degree threshold forcing a perfect $F$-tiling in a graph $G$ has a long history, culminating in the Kühn-Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs $F$. We initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs $F$ this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect $P$-tiling in an edge-ordered graph, where $P$ is any fixed monotone path.

Pages:
74–81
References

Noga Alon and Raphael Yuster. H-factors in dense graphs. Journal of Combinatorial Theory, Series B, 66(2), 269-282, 1996.
https://doi.org/10.1006/jctb.1996.0020

Igor Araujo, Simón Piga, Andrew Treglown, and Zimu Xiang. Tiling edge-ordered graphs with monotone paths and other structures. arXiv preprint arXiv:2305.07294, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-010

Jozsef Balogh, Li Lina, and Andrew Treglown. Tilings in vertex ordered graphs. Journal of Combinatorial Theory, Series B 155: 171-201, 2022.
https://doi.org/10.1016/j.jctb.2022.02.006

Matija Bucić, Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran, and Adam Zsolt Wagner. Nearly-linear monotone paths in edge-ordered graphs. Israel Journal of Mathematics 238 (2): 663-685, 2020.
https://doi.org/10.1007/s11856-020-2035-7

Alewyn P. Burger, Ernest J. Cockayne, and Christina M. Mynhardt. Altitude of small complete and complete bipartite graphs. Australasian Journal of Combinatorics 31: 167-177, 2005.

Robert A. Calderbank, Fan R.K. Chung, and Dean G. Sturtevant. Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs. Discrete mathematics 50: 15-28, 1984.
https://doi.org/10.1016/0012-365X(84)90031-1

Václav Chvátal and János Komlós. Some combinatorial theorems on monotonicity. Canadian Mathematical Bulletin 14(2): 151-157, 1971.
https://doi.org/10.4153/CMB-1971-028-8

Corradi, Keresztély and András Hajnal. On the maximal number of independent circuits in a graph. Acta Mathematica Hungarica 14(3-4): 423-439, 1963.
https://doi.org/10.1007/BF01895727

Andrea Freschi and Andrew Treglown. Dirac-type results for tilings and coverings in ordered graphs. In Forum of Mathematics, Sigma. 10: e104, 2022.
https://doi.org/10.1017/fms.2022.92

Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Dömötör Pálvölgyi, Gábor Tardos, and Máté Vizer. Turán problems for edge-ordered graphs. Journal of Combinatorial Theory, Series B, 160: 66-113, 2023.
https://doi.org/10.1016/j.jctb.2022.12.006

Ronald L. Graham and Daniel J. Kleitman. Increasing paths in edge ordered graphs. Periodica Mathematica Hungarica 3(1-2): 141-148, 1973.
https://doi.org/10.1007/BF02018469

András Hajnal and Endre Szemerédi, Proof of a conjecture of P. Erdős, In Combinatorial Theory and its Application 2: 601-623, 1970.

János Komlós. Tiling turán theorems. Combinatorica 20: 203-218, 2000.
https://doi.org/10.1007/s004930070020

János Komlós, Gábor Sárkozy, and Endre Szemerédi. Proof of the Alon-Yuster conjecture. Discrete Mathematics 235(1-3): 255-269, 2001.
https://doi.org/10.1016/S0012-365X(00)00279-X

Daniela Kühn and Deryk Osthus. The minimum degree threshold for perfect graph packings.Combinatorica 29(1): 65-107, 2009.
https://doi.org/10.1007/s00493-009-2254-3

Allan Lo and Klas Markström. F-Factors in hypergraphs via absorption. Graphs and Combinatorics 31: 679-712, 2015.
https://doi.org/10.1007/s00373-014-1410-8

Kevin G. Milan. Monotone paths in dense edge-ordered graphs. Journal of Combinatorics, 8(3): 423-437, 2017.
https://doi.org/10.4310/JOC.2017.v8.n3.a2

Jaroslav Nešetřil and Vojtěch Rödl. Statistics of orderings. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 421-433, 2017.
https://doi.org/10.1007/s12188-016-0174-x

Rödl, Vojtěch. Master's thesis. Charles University, 1973.

Metrics

0

Views

0

PDF views