Ir al contenido

Documat

Cuestiones existenciales en combinatoria y teoría de números: el método probabilístico

  • Morales López, Ismael [1]
    1. [1] Universidad Autónoma de Madrid

      Universidad Autónoma de Madrid

      Madrid, España

  • Localización: TEMat: Divulgación de trabajos de estudiantes de matemáticas, ISSN-e 2530-9633, Nº. 4, 2020, págs. 43-65
  • Idioma: español
  • Enlaces
  • Resumen
    • español

      La probabilidad es una rama de las matemáticas indispensable en la formulación de muchos fenómenos físicos y, en general, de procesos que contengan algún tipo de arbitrariedad. Un aspecto menos conocido de esta es el poder que puede llegar a tener en cuestiones de naturaleza discreta.

      El método probabilístico es una herramienta que parte de una idea muy limpia y prometedora. Con el fin de demostrar la existencia de un objeto $C$ caracterizado por una determinada propiedad $P$, se embebe $C$ en un espacio de probabilidad y se demuestra que el suceso correspondiente a tener la propiedad $P$ ocurre con probabilidad positiva.

      El objetivo de este artículo es sentar la base teórica tras la cual subyace esta técnica y presentar varias aplicaciones en problemas relacionados con la combinatoria y la teoría de números.

    • English

      Probability is an indispensable branch of mathematics when it comes to formulating many physical phenomena and, in general, processes which contain some arbitrariness. A less-known aspect is the power it can achieve when tackling questions of discrete nature.

      The probabilistic method is a tool based on a neat and promising idea. With the aim of proving the existence of an object $C$ characterised by some property $P$, $C$ is embedded in a probability space and it is proved that the event corresponding to having property $P$ holds with positive probability.

      The objective of this paper is to set the theoretical background that rests behind this technique and to present some applications in problems with a combinatorial or number-theoretic flavour.

  • Referencias bibliográficas
    • ALON, Noga yKLEITMAN, Daniel J. «Sum-free subsets». En:A tribute to Paul Erdős. Ed. por Baker,Alan; Bollobás, Béla, y Hajnal, András. Cambridge:...
    • ALON, Noga ySPENCER, Joel H.The probabilistic method. With an appendix on the life and work ofPaul Erdős. 2.aed. Wiley-Interscience Series...
    • ALON, Noga. «Paul Erdős and the Probabilistic Method». En:Notices of the American MathematicalSociety62.3 (2015), págs. 226-230.ISSN: 0002-9920.https://doi.org/10.1090/noti1223.
    • BECK, József. «An algorithmic approach to the Lovász local lemma. I». En:Random Structures &Algorithms2.4 (1991), págs. 343-365. ISSN:...
    • BILLINGSLEY, Patrick.Probability and measure. 3.aed. Wiley Series in Probability and MathematicalStatistics. Nueva York: Wiley-Interscience,...
    • BOLLOBÁS, Béla.Graph theory. An introductory course. Vol. 63. Graduate Texts in Mathematics. NuevaYork-Berlín: Springer-Verlag, 1979.https://doi.org/10.1007/978-1-4612-9967-7.
    • BOPPANA, Ravi.Unexpected Uses of Probability. 2005.URL:http://www.aops.com/Forum/viewtopic.php?p=1943887#p1943887/.
    • BOREL, Émile. «Les probabilités dénombrables et leurs applications arithmétiques». En:Rendicontidel Circolo Matematico di Palermo27 (1909),...
    • BOURGAIN, Jean. «Estimates related to sumfree subsets of sets of integers». En:Israel Journal ofMathematics97 (1997), págs. 71-92.ISSN: 0021-2172.https://doi.org/10.1007/BF02774027.
    • CHATTOPADHYAY, Eshan yZUCKERMAN, David. «Explicit two-source extractors and resilient functions».En:Annals of Mathematics. Second Series189.3...
    • CHEN, Evan. «Expected Uses of Probability». En:Mathematical reflections6 (2014).URL:https://web.evanchen.cc/handouts/ProbabilisticMethod/ProbabilisticMethod.pdf.
    • COHEN, Gil. «Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs». En:STOC’16—Proceedings of the 48th Annual ACM...
    • DAVIDOFF, Giuliana;SARNAK, Peter, yVALETTE, Alain.Elementary number theory, group theory, andRamanujan graphs.Vol. 55. London Mathematical...
    • DJUKIĆ, Dušan;JANKOVIĆ, Vladimir;MATIĆ, Ivan, yPETROVIĆ, Nikola.The IMO Compendium. 2.aed.Problem Books in Mathematics. Nueva York: Springer-Verlag,...
    • EBERHARD, Sean;GREEN, Ben, yMANNERS, Freddie. «Sets of integers with no large sum-free subset».En:Annals of Mathematics. Second Series180.2...
    • ERDÖS, Paul yKAC , Mark. «The Gaussian law of errors in the theory of additive number theoreticfunctions». En:American Journal of Mathematics62...
    • ERDÖS, Paul yLOVÁSZ, László. «Problems and results on3-chromatic hypergraphs and some relatedquestions». En:Infinite and finite sets (Colloq.,...
    • ERDÖS, Paul. «Applications of probability to combinatorial problems». En:Colloquium on Combina-torial Methods in Probability Theory. 1962,...
    • ERDÖS, Paul. «Extremal problems in number theory». En:Proceedings of Symposia in Pure Mathe-matics. Vol. VIII. Providence, Rhode Island: American...
    • ERDÖS, Paul. «On a problem in graph theory». En:The Mathematical Gazette47 (1963), págs. 220-223.ISSN: 0025-5572.https://doi.org/10.2307/3613396
    • ERDÖS, Paul. «Some remarks on the theory of graphs». En:Bulletin of the American MathematicalSociety53 (1947), págs. 292-294. ISSN: 0002-9904.https://doi.org/10.1090/S0002-9904-1947-08785-1.
    • FERNÁNDEZ, Pablo yFERNÁNDEZ, José Luis. «El discreto encanto de la matemática». 2018.URL:http://verso.mat.uam.es/~pablo.fernandez/.
    • GOWERS, William T. «Quasirandom groups». En:Combinatorics, Probability and Computing17.3(2008), págs. 363-387.ISSN: 0963-5483.https://doi.org/10.1017/S0963548307008826.
    • GREEN, Ben yTAO , Terence. «The primes contain arbitrarily long arithmetic progressions». En:Annalsof Mathematics. Second Series167.2 (2008),...
    • LOH, Po-Shen.Probabilistic method in combinatorics. 2009.URL:http://www.math.cmu.edu/~ploh/public_html/olympiad.shtml.
    • MARGULIS, Grigori A. «Explicit constructions of expanders». En:Problemy Peredači Informacii9.4(1973), págs. 71-80.ISSN: 0555-2923.
    • MERTENS, Franz. «Ein Beitrag zur analytischen Zahlentheorie». En:Journal für die reine und ange-wandte Mathematik78 (1874), págs. 46-62. ISSN:...
    • MOLLOY, Michael yREED, Bruce.Graph colouring and the probabilistic method. Vol. 23. Algorithmsand Combinatorics. Berlín: Springer-Verlag,...
    • MOSER, Robin A. «A constructive proof of the Lovász local lemma». En:STOC’09—Proceedings of the2009 ACM International Symposium on Theory...
    • MOSER, Robin A. yTARDOS, Gábor. «A constructive proof of the general Lovász local lemma». En:Journal of the ACM57.2 (2010).ISSN: 0004-5411.https://doi.org/10.1145/1667053.1667060.
    • RAMSEY, Frank P. «On a Problem of Formal Logic». En:Proceedings of the London MathematicalSociety. Second Series30.4 (1929), págs. 264-286....
    • RIORDAN, Oliver.Lecture notes on Probabilistic Combinatorics. 2019.URL:https://courses.maths.ox.ac.uk/node/view_material/41048.
    • RIORDAN, Oliver.Oxford materials about the course on Probabilistic Combinatorics. 2019.URL:https://courses.maths.ox.ac.uk/node/view_material/41304.
    • SHEARER, Jean B. «On a problem of Spencer». En:Combinatorica5.3 (1985), págs. 241-245. ISSN:0209-9683.https://doi.org/10.1007/BF02579368.
    • SIPSER, Michael ySPIELMAN, Daniel A. «Expander codes». En:IEEE Transactions on InformationTheory42.6 (1996). Codes and complexity, págs. 1710-1722.ISSN:...
    • SPENCER, Joel. «Ramsey’s Theorem — A New Lower Bound». En:Journal of Combinatorial Theory.Series A18.1 (1975), págs. 108-115. ISSN: 0097-3165.https://doi.org/10.1016/0097-3165(75)90071-0.
    • SZELE, Tibor. «Kombinatorikai vizsgálatok az irányitott teljes gráffal». En:Matematikai és FizikaiLapok50 (1943), págs. 223-256.
    • TAO , Terence.Moser’s entropy compression argument. 2009.URL:https://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression-argument/.
    • TAO ,Terence yVU,Van.Additivecombinatorics.Vol. 105. Cambridge Studies in Advanced Mathematics.Cambridge: Cambridge University Press, 2006.https://doi.org/10.1017/CBO9780511755149
    • TURÁN, Paul. «On a Theorem of Hardy and Ramanujan». En:The Journal of the London MathematicalSociety9.4 (1934), págs. 274-276.ISSN: 0024-6107.https://doi.org/10.1112/jlms/s1-9.4.274.
    • WIKIPEDIA.List of probabilistic proofs of non-probabilistic theorems. En:Wikipedia, The Free Encyclo-pedia. 2019.URL:https://en.wikipedia.org/w/index.php?title=List_of_probabilistic_proofs_of_non-probabilistic_theorems&oldid=910281376.
    • WIKIPEDIA.Lovász local lemma. En:Wikipedia, The Free Encyclopedia. 2019.URL:https://en.wikipedia.org/w/index.php?title=Lov%5C%C3%5C%A1sz_local_lemma&oldid=895002723.
    • WIKIPEDIA.Problema de satisfacibilidad booleana. En:Wikipedia, La enciclopedia libre. 2019.URL:https://es.wikipedia.org/w/index.php?title=Problema_de_satisfacibilidad_booleana&oldid=117829273.
    • WIKIPEDIA.Ramsey’s theorem. En:Wikipedia, The Free Encyclopedia. 2020.URL:https://en.wikipedia.org/w/index.php?title=Ramsey%5C%27s_theorem&oldid=937680845.
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno