More Like this

1. Unavoidable Patterns and Plane Paths in Dense Topological Graphs

   https://doi.org/10.4230/lipics.socg.2026.63  

   Keszegh, Balázs; Suk, Andrew; Tardos, Gábor; Zeng, Ji (January 2026, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ahn, Hee-Kap; Hoffmann, Michael; Nayyeri, Amir (Ed.)

   Abstract: Let C_{s,t} be the complete bipartite geometric graph, with s and t vertices on two distinct parallel lines respectively, and all s t straight-line edges drawn between them. In this paper, we show that every complete bipartite simple topological graph, with parts of size 2(k-1)⁴ + 1 and 2^{k^{5k}}, contains a topological subgraph weakly isomorphic to C_{k,k}. As a corollary, every n-vertex simple topological graph not containing a plane path of length k has at most O_k(n^{2 - 8/k⁴}) edges. When k = 3, we obtain a stronger bound by showing that every n-vertex simple topological graph not containing a plane path of length 3 has at most O(n^{4/3}) edges. We also prove that x-monotone simple topological graphs not containing a plane path of length 3 have at most a linear number of edges. 

   more » « less
2. Unavoidable Patterns in Complete Simple Topological Graphs

   Andrew Suk, Ji Zeng (January 2023, Graph Drawing and Network Visualization: 30th International Symposium, GD 2022, Tokyo, Japan, September 13–16, 2022, Revised Selected Papers)

   Angelini, P. (Ed.)

   We show that every complete n-vertex simple topological graph contains a topological subgraph on at least (logn)1/4−o(1) vertices that is weakly isomorphic to the complete convex geometric graph or the complete twisted graph. This is the first improvement on the bound Ω(log1/8n) obtained in 2003 by Pach, Solymosi, and Tóth. We also show that every complete n-vertex simple topological graph contains a plane path of length at least (logn)1−o(1) . 

   more » « less
3. Tight paths in convex geometric hypergraphs

   https://doi.org/10.19086/aic.12044  

   Mubayi, Dhruv; Füredi, Zoltán; Verstraëte, Jacques; Kostochka, Alexandr; Jiang, Tao (February 2020, Advances in Combinatorics)

   One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $$n$$-vertex graph with more than $$\frac{k-1}{2}n$$ edges contains any $$k$$-edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $$r$$-uniform hypergraph, i.e., a hypergraph where each edge contains $$r$$ vertices. A tight tree is an $$r$$-uniform hypergraph such that there is an ordering $$v_1,\ldots,v_n$$ of its its vertices with the following property: the vertices $$v_1,\ldots,v_r$$ form an edge and for every $i>r$, there is a single edge $$e$$ containing the vertex $$v_i$$ and $r-1$ of the vertices $$v_1,\ldots,v_{i-1}$$, and $$e\setminus\{v_i\}$$ is a subset of one of the edges consisting only of vertices from $$v_1,\ldots,v_{i-1}$$. The conjecture of Kalai asserts that every $$n$$-vertex $$r$$-uniform hypergraph with more than $$\frac{k-1}{r}\binom{n}{r-1}$$ edges contains every $$k$$-edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $$n$$ for every $$r$$ and $$k$$.The article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $$r$$-tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous Erdős-Gallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first non-trivial upper bound valid for all $$r$$ and $$k$$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices. 

   more » « less
4. On asymptotic packing of convex geometric and ordered graphs

   https://doi.org/10.1002/jgt.23002  

   Nie, Jiaxi; Surya, Erlang; Zeng, Ji (December 2023, Journal of Graph Theory)

   Abstract A convex geometric graph is said to be packable if there exist edge‐disjoint copies of in the complete convex geometric graph covering all but edges. We prove that every convex geometric graph with cyclic chromatic number at most 4 is packable. With a similar definition of packability for ordered graphs, we prove that every ordered graph with interval chromatic number at most 3 is packable. Arguments based on the average length of edges imply these results are the best possible. We also identify a class of convex geometric graphs that are packable due to having many “long” edges. 

   more » « less
5. Monochromatic Subgraphs in Iterated Triangulations

   https://doi.org/10.37236/9292  

   Ma, Jie; Tang, Tianyun; Yu, Xingxing (October 2020, The Electronic Journal of Combinatorics)

   null (Ed.)

   For integers $$n\ge 0$$, an iterated triangulation $$\mathrm{Tr}(n)$$ is defined recursively as follows: $$\mathrm{Tr}(0)$$ is the plane triangulation on three vertices and, for $$n\ge 1$$, $$\mathrm{Tr}(n)$$ is the plane triangulation obtained from the plane triangulation $$\mathrm{Tr}(n-1)$$ by, for each inner face $$F$$ of $$\mathrm{Tr}(n-1)$$, adding inside $$F$$ a new vertex and three edges joining this new vertex to the three vertices incident with $$F$$. In this paper, we show that there exists a 2-edge-coloring of $$\mathrm{Tr}(n)$$ such that $$\mathrm{Tr}(n)$$ contains no monochromatic copy of the cycle $$C_k$$ for any $$k\ge 5$$. As a consequence, the answer to one of two questions asked by Axenovich et al. is negative. We also determine the radius 2 graphs $$H$$ for which there exists $$n$$ such that every 2-edge-coloring of $$\mathrm{Tr}(n)$$ contains a monochromatic copy of $$H$$, extending a result of Axenovich et al. for radius 2 trees. 

   more » « less