Kucheriya, Gaurav and Tardos, Gábor (2023) A Characterization of Edge-Ordered Graphs with Almost Linear Extremal Functions. COMBINATORICA, 43. pp. 1111-1123. ISSN 0209-9683
|
Text
2206.12979v2.pdf Download (417kB) | Preview |
Abstract
The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. (Turán problems for Edge-ordered graphs, 2021). They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are n(1+o(1)). Here we resolve this conjecture proving the stronger upper bound of n2(O(vlog n)). This represents a gap in the family of possible extremal functions as other forbidden edge-ordered graphs have extremal functions O(n(C)) for some c > 1. However, our result is probably not the last word: here we conjecture that the even stronger upper bound of n log(O(1)) n also holds for the same set of extremal functions.
| Item Type: | Article |
|---|---|
| Additional Information: | Export Date: 15 January 2024 Correspondence Address: Tardos, G.; Alfréd Rényi Institute of MathematicsHungary; email: tardos@renyi.hu Funding details: Horizon 2020 Framework Programme, H2020 Funding details: H2020 Marie Skłodowska-Curie Actions, MSCA, 823748 Funding details: European Research Council, ERC Funding details: Grantová Agentura České Republiky, GA ČR, 22-19073S Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFI, K-132696, SNN-135643 Funding text 1: We are grateful for the comments of Mykhaylo Tyomkyn improving the presentation of this paper. The ERC Advanced Grant “GeoSpace” made it possible for the first author to visit Rényi Institute in the Fall of 2021 and helped enormously with the collaboration resulting in this paper. Supported by GAČR Grant 22-19073S and European Union’s Horizon 2020 Research and Innovation Programme under the Marie Skłodowska-Curie Grant Agreement No. 823748. Supported by the National Research, Development and Innovation Office, NKFIH Projects K-132696 and SNN-135643 and by the ERC Advanced Grant “GeoScape”. |
| Uncontrolled Keywords: | extremal graph theory; Turán number; edge-ordered graphs; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 30 Mar 2024 10:56 |
| Last Modified: | 30 Mar 2024 10:56 |
| URI: | https://real.mtak.hu/id/eprint/191297 |
Actions (login required)
 |
Edit Item |
