El teorema de Lekkerkerker-Boland, o cómo resolver un crimen usando teoría de grafos

• Mercedes Flores Fernández ^[1]
  1. [1] Universidad de Murcia

     Universidad de Murcia

     Murcia, España

     
• Localización: Materials matemàtics, ISSN-e 1887-1097, Nº. 0, 2025
• Idioma: español
• Enlaces
  • Texto completo
• Resumen

  • Este artículo propone al lector un doble divertimento, matemático y literario. Por una parte, se presenta una prueba, autocontenida y accesible para los no versados en la materia, de un sofisticado resultado de la teoría de grafos. Por otra se muestra cómo, contra todo pronóstico, dicho teorema puede usarse como piedra angular sobre la que construir la trama de un relato de ficción detectivesca.

• Referencias bibliográficas
  • ] E. A. Abbott, Flatland: a romance of many dimensions, Seeley & Co., Londres, 1884. Trad. al castellano de J. Villa: Planilandia, Guadarrama, Barcelona,...
  • S. Benzer, «On the topology of the genetic fine structure», Proc. Nat. Acad. Sci. U.S.A. 45 (1959), 1607–1620.
  • S. Benzer, «The fine structure of the gene», Sci. Amer. 206 (1962), 70–84.
  • C. Berge, Théorie des graphes et ses applications, Dunod, París, 1958.
  • C. Berge, Qui a tué le duc de Densmore?, La Bibliothèque Oulipienne 67, OuLiPo, París, 1994. Trad. al inglés de I. White: «Who killed the Duke...
  • J. L. Borges, Ficciones, Sur, Buenos Aires, 1944
  • D. Bouyssou, O. Hudry y D. de Werra, «Claude Berge and the “Oulipo”», EURO Newsletter #6, 2006. https://www.lamsade.dauphine.fr/~bouyssou/Berge.pdf
  • P. Buneman, «A characterization of rigid circuit graphs», Discrete Math. 9 (1974), 205–212.
  • I. Calvino, Se una notte d’inverno un viaggiatore, Einaudi, Turín, 1979. Trad. al castellano de E. Benítez: Si una noche de invierno un viajero, Bruguera,...
  • K. Cameron, C. T. Hoàng y B. Lévêque, Asteroids in rooted and directed path graphs, Wilfrid Laurier University, 2008. https://arxiv.org/pdf/ 0812.2734.pdf
  • K. Cameron, C. T. Hoàng y B. Lévêque, «Asteroids in rooted and directed path graphs», Electron. Notes Discrete Math. 32 (2009), 67–74.
  • K. Cameron, C. T. Hoàng y B. Lévêque, «Characterizing directed path graphs by forbidden asteroids», J. Graph Theory 68 (2011), 103–112.
  • G. Chartrand, L. Lesniak y P. Zhang, Graphs & digraphs. Sixth edition, CRC Press, Boca Ratón, 2016.
  • T. Chiang, «Division by zero», en: Stories of your life and others, Tor Books, Nueva York, 2002, pp. 93–116. Trad. al castellano de L. G....
  • M. Chudnovsky, N. Robertson, P. Seymour y R. Thomas, «The strong perfect graph theorem», Annals of Math. (2) 164 (2006), 51–229.
  • G. A. Dirac, «On rigid circuit graphs», Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76.
  • M. Flores Fernández, El teorema de Lekkerkerker-Boland, o cómo resolver un crimen usando teoría de grafos, trabajo fin de grado, Universidad de...
  • D. R. Fulkerson y O. A. Gross, «Incidence matrices and interval graphs», Pacific J. Math. 15 (1965), 835–855.
  • N. Gaiman, «Other people», en: Fragile things, Headline Review, Londres, 2006, pp. 123–126. Trad. al castellano de M. Faerna: «Los otros», en:...
  • M. Gardner, «The no-sided professor», en: Fantasia mathematica, Clifton Fadiman (ed.), Simon & Schuster, Nueva York, 1958, pp. 99–109....
  • F. Gavril, «The intersection graphs of subtrees in trees are exactly the chordal graphs», J. Combinatorial Theory Ser. B 16 (1974), 47–56.
  • J. R. Gilbert, D. J. Rose y A. Edenbrandt, «A separator theorem for chordal graphs», SIAM J. Algebraic Discrete Methods 5 (1984), 306– 313.
  • P. C. Gilmore y A. J Hoffman, «A characterization of comparability graphs and of interval graphs», Canad. J. Math. 16 (1964), 539–548.
  • M. C. Golumbic, Algorithmic graph theory and perfect graphs. Second edition, Annals of Discrete Mathematics 57, Elsevier Science B.V., Ámsterdam,...
  • M. Haddon, The curious incident of the dog in the night-time, Jonathan Cape, Londres, 2003. Trad. al castellano de P. Antón de Vez: El curioso incidente...
  • A. Hajnal and J. Surányi, «Über die Auflösung von Graphen in vollständige Teilgraphen», Ann. Univ. Sci. Budapest, Eötvös, Sect. Math. 1 (1958),...
  • G. Hajós, «Über eine Art von Graphen», Intern. Math. Nachr. 11 (1957), problema 65.
  • R. Halin, «Some remarks on interval graphs», Combinatorica 2 (1982), 297–304.
  • C.-W. Ho y R. C. T. Lee, «Counting clique trees and computing perfect elimination schemes in parallel», Inform. Process. Lett. 31 (1989),...
  • E. Jardiel Poncela, El libro del convaleciente, Hispania, Zaragoza, 1938. [31] A. Kasman, Mathematical Fiction, College of Charleston, 2000....
  • C. G. Lekkerkerker y J. Ch. Boland, «Representation of a finite graph by a set of intervals on the real line», Fund. Math. 51 (1962/1963), 45–64.
  • M. Macho Stadler, OuLiPo: juegos matemáticos en la literatura, Universidad del País Vasco, 2012. https://www.ehu.eus/~mtwmastm/OuLiPo_ Bak2012.pdf
  • M. Macho Stadler, «OuLiPo: un viaje desde las matemáticas a la literatura», Tropelías 25 (2016), 129–146.
  • T. A. McKee y F. R. McMorris, Topics in intersection graph theory, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Filadelfia,...
  • F. O’Brien, The third policeman, MacGibbon & Kee, Londres, 1967. Trad. al castellano de J. Fibla: El tercer policía, Montesinos Editor, Barcelona,...
  • G. Perec, La Vie, mode d?emploi, Hachette, París, 1978. Trad. al castellano de J. Escué: La vida instrucciones de uso, Anagrama, Barcelona 1988.
  • R. Queneau, Exercices de style, Gallimard, París, 1947. Trad. al castellano de A. Fernández Ferrer: Ejercicios de estilo, Cátedra, Madrid, 1989.
  • F. S. Roberts, Discrete mathematical models, with applications to social, biological and environmental problems, Prentice-Hall, Englewood...
  • D. J. Rose, «A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations», en: Graph theory...
  • B. Toft, «Claude Berge — sculptor of graph theory», en: Graph theory in Paris (A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier y J. L. Ramírez...
  • M. de Unamuno, Niebla, Renacimiento, Madrid, 1914.
  • S. S. Van Dine, The bishop murder case, Scribners Press, Nueva York, 1929. Trad. al castellano de I. Miller: Los crímenes del «Obispo», Edicomunicación,...
  • J. R. Walter, Representations of rigid cycle graphs, tesis doctoral, Wayne State University, 1972.