On edge-ordered graphs with linear extremal functions

EUROCOMB’23

Abstract
The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear extremal functions. This characterization is similar in spirit to results of Füredi et al. (2020) about vertex-ordered and convex geometric graphs.

Pages:
688–694
References

P. Brass, Gy. Károlyi, P. Valtr, A Turán-type extremal theory of convex geometric graphs, Discrete and Computational Geometry--The Goodman-Pollack Festschrift (B. Aronov et al., eds.), Springer-Verlag, Berlin, 2003, 277-302.
https://doi.org/10.1007/978-3-642-55566-4_12

B. Keszegh, D. Pálvölgyi, The number of tangencies between two families of curves, manuscript, arXiv:2111.08787.

Z. Füredi, A. Kostochke, D. Mubayi, J. Verstraëte, Ordered and convex geometric trees with linear extremal function, Discrete & Computational Geometry 64 (2020), 324-338.
https://doi.org/10.1007/s00454-019-00149-z

D. Gerbner, A. Methuku, D. Nagy, D. Pálvölgyi, G. Tardos, M. Vizer, Edge-ordered Turán problems, Journal of Combinatorial Theory, Ser. B 160 (2023), 66-113.
https://doi.org/10.1016/j.jctb.2022.12.006

G. Kucheriya, Master's thesis, Moscow Institute of Physics and Technology, 2021.

G. Kucheriya, G. Tardos, A characterization of edge-ordered graphs with almost linear extremal functions, Combinatorica (to appear), arXiv:2206.12979.

J. Pach, G. Tardos, Forbidden paths and cycles in ordered graphs and matrices, Israel Journal of Mathematics 155 (2006), 359-380.
https://doi.org/10.1007/BF02773960

Metrics

0

Views

0

PDF views