Information Technology Reference
In-Depth Information
4
Concluding Remarks
1. We showed that for every integer
t
, the maximumnumber of edges in a simple topo-
logical graph with
n
vertices that does not contain
t
edges all disjoint from another set of
t
edges is
cn
,where
c
=
c
(
t
). A careful analysis of the proof shows that
c
=2
O
(
t
log
t
)
.
It would be interesting to see if one could improve the upper bound on
c
to
O
(
t
).
2. We suspect that the bounds of 200 and 400 in Lemma 4 and Proposition 1 are not
optimal. Since any constant bound yields a linear upper bound for the number of edges
in tangled-thrackles, we have not optimized these values. However, finding the best
possible constants, or shorter proofs for some arbitrary constant bounds, would be of
interest.
Acknowledgments.
We would like to thank Gábor Tardos for some suggestions on
how to simplify the main proof.
References
1. Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York
(2005)
2. Fulek, R., Pach, J.: A computational approach to Conway's thrackle conjecture. Computa-
tional Geometry: Theory and Applications 44, 345-355 (2011)
3. Fulek, R., Ruiz-Vargas, A.J.: Topological graphs: empty triangles and disjoint matchings. In:
Proc. SymposiumonComputational Geometry, pp. 259-266. ACM Press (2013)
4. Lovász, L., Pach, J., Szegedy, M.: On Convway's trackle conjecture. Discrete & Compua-
tional Geometry 18, 369-376 (1998)
5. Matousek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212.
Springer (2002)
6. Nivasch, G.: Improved bounds and new techniques for Davenport-Schinzel sequences and
their generalizations. JACM 57(3), article 17 (2010)
7. Pach, J.: Geometric graph theory. In: Goodman, J., O'Rourke, J. (eds.) Handbook of Discrete
and Computational Geometry, 2nd edn., ch. 10. CRC Press, Boca Rotan (2007)
8. Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley, New York (1995)
9. Pach, J., Radoicic, R., Tóth, G.: Tangled thrackles. In: M
á
rquez, A., Ramos, P., Urrutia, J.
(eds.) EGC 2011. LNCS, vol. 7579, pp. 45-53. Springer, Heidelberg (2012)
10. Pach, J., Tóth, G.: Disjoint edges in topological graphs. In: Akiyama, J., Baskoro, E.T., Kano,
M. (eds.) IJCCGGT 2003. LNCS, vol. 3330, pp. 133-140. Springer, Heidelberg (2005)
11. Pach, J., Sterling, E.: Conway's conjecture for monotone thrackles. American Mathematical
Monthly 118(6), 544-548 (2011)
12. Pach, J., Tóth, G.: Which crossing number is it anyway? J. Comb. Theory Ser. B 80, 225-246
(2000)
13. Pettie, S.: Sharp bounds on Davenport-Schinzel sequences of every order. In: Proc. Sympo-
siumonComputational Geometry, pp. 319-328. ACM Press (2013)
14. Sharir, M., Agarwal, P.K.: Devenport-Schinzel Sequences and their Geometric Applications.
Cambridge University Press (1995)
15. Suk, A.: Density theorems for intersection graphs of
t
-monotone curves. SIAM Journal on
Discrete Mathematics 27, 1323-1334 (2013)
16. Suk, A.: Disjonit edges in complete toplogical graphs. Discrete & Computational Geome-
try 49, 280-286 (2013)
