A sharp threshold phenomenon in string graphs. (English) Zbl 1480.05038
Summary: A string graph is the intersection graph of curves in the plane. We prove that for every \(\epsilon >0\), if \(G\) is a string graph with \(n\) vertices such that the edge density of \(G\) is below \({1}/{4}-\epsilon \), then \(V(G)\) contains two linear sized subsets \(A\) and \(B\) with no edges between them. The constant 1/4 is a sharp threshold for this phenomenon as there are string graphs with edge density less than \({1}/{4}+\epsilon\) such that there is an edge connecting any two logarithmic sized subsets of the vertices. The existence of linear sized sets \(A\) and \(B\) with no edges between them in sufficiently sparse string graphs is a direct consequence of a recent result of J. R. Lee [LIPIcs – Leibniz Int. Proc. Inform. 67, Article 1, 8 p. (2017; Zbl 1402.05151)] about separators. Our main theorem finds the largest possible density for which this still holds. In the special case when the curves are \(x\)-monotone, the same result was proved by J. Pach and I. Tomon [Eur. J. Comb. 82, Article ID 102994, 12 p. (2019; Zbl 1419.05065)], who also proposed the conjecture for the general case.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C12 | Distance in graphs |
References:
| [1] | Benzer, S., On the topology of the genetic fine structure, Proc. Natl. Acad. Sci. USA, 45, 11, 1607-1620 (1959) · doi:10.1073/pnas.45.11.1607 |
| [2] | Chudnovsky, M., Scott, A., Seymour, P., Spirkl, S.: Sparse graphs without linear anticomplete pairs (2018). arXiv:1804.01060v1 · Zbl 1458.05171 |
| [3] | Chojnacki, Ch, Über wesentlich unplättbare Kurven im dreidimensionalen Raume, Fund. Math., 23, 135-142 (1934) · JFM 60.0528.02 · doi:10.4064/fm-23-1-135-142 |
| [4] | Fox, J., A bipartite analogue of Dilworth’s theorem, Order, 23, 2-3, 197-209 (2006) · Zbl 1108.06002 · doi:10.1007/s11083-006-9043-z |
| [5] | Fox, J., Pach, J.: Erdős-Hajnal-type results on intersection patterns of geometric objects. In: Horizons of Combinatorics (Balatonalmádi 2006). Bolyai Soc. Math. Stud., vol. 17, pp. 79-103. Springer, Berlin (2008) · Zbl 1170.05327 |
| [6] | Fox, J.; Pach, J., A separator theorem for string graphs and its applications, Comb. Probab. Comput., 19, 3, 371-390 (2010) · Zbl 1230.05186 · doi:10.1017/S0963548309990459 |
| [7] | Fox, J.; Pach, J., String graphs and incomparability graphs, Adv. Math., 230, 3, 1381-1401 (2012) · Zbl 1244.05073 · doi:10.1016/j.aim.2012.03.011 |
| [8] | Fox, J.; Pach, J., Applications of a new separator theorem for string graphs, Comb. Probab. Comput., 23, 1, 66-74 (2014) · Zbl 1287.05066 · doi:10.1017/S0963548313000412 |
| [9] | Fox, J.; Pach, J.; Tóth, CD, Turán-type results for partial orders and intersection graphs of convex sets, Israel J. Math., 178, 29-50 (2010) · Zbl 1248.05118 · doi:10.1007/s11856-010-0056-3 |
| [10] | Fox, J.; Pach, J.; Tóth, CD, Intersection patterns of curves, J. Lond. Math. Soc., 83, 2, 389-406 (2011) · Zbl 1238.05269 · doi:10.1112/jlms/jdq087 |
| [11] | Hardy, GH; Littlewood, JE; Pólya, G., Inequalities (1952), Cambridge: Cambridge University Press, Cambridge · Zbl 0047.05302 |
| [12] | Lee, J.R.: Separators in region intersection graphs. In: 8th Innovations in Theoretical Computer Science Conference. Leibniz Int. Proc. Inform., vol. 67, # 1. Leibniz-Zent. Inform., Wadern (2017) · Zbl 1402.05151 |
| [13] | Lipton, RJ; Tarjan, RE, A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 2, 177-189 (1979) · Zbl 0432.05022 · doi:10.1137/0136016 |
| [14] | Matoušek, J., Near-optimal separators in string graphs, Comb. Probab. Comput., 23, 1, 135-139 (2014) · Zbl 1287.05094 · doi:10.1017/S0963548313000400 |
| [15] | Pach, J.; Reed, B.; Yuditsky, Y., Almost all string graphs are intersection graphs of plane convex sets, Discrete Comput. Geom., 63, 4, 888-917 (2020) · Zbl 1442.05189 · doi:10.1007/s00454-020-00213-z |
| [16] | Pach, J., Tomon, I.: Ordered graphs and large bi-cliques in intersection graphs of curves. Eur. J. Comb. 82, # 102994 (2019) · Zbl 1419.05065 |
| [17] | Pach, J.; Tóth, G., How many ways can one draw a graph?, Combinatorica, 26, 5, 559-576 (2006) · Zbl 1121.05006 · doi:10.1007/s00493-006-0032-z |
| [18] | Sinden, FW, Topology of thin film RC-circuits, Bell Syst. Tech. J., 45, 9, 1639-1662 (1966) · Zbl 0144.45601 · doi:10.1002/j.1538-7305.1966.tb01713.x |
| [19] | Szemerédi, E.: Regular partitions of graphs. In: Problemes Combinatoires et Théorie des Graphes (Orsay 1976). Colloq. Internat. CNRS, vol. 260, pp. 399-401. CNRS, Paris (1978) · Zbl 0413.05055 |
| [20] | Turán, P., Egy gráfelméleti szélsőérték feladatról, Matematikai és Fizikai Lapok, 48, 436-452 (1941) · Zbl 0026.26903 |
| [21] | Tutte, WT, Toward a theory of crossing numbers, J. Comb. Theory, 8, 45-53 (1970) · Zbl 0187.20803 · doi:10.1016/S0021-9800(70)80007-2 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
