Resumen de Grafs aleatoris: teoria i aplicacions, de la naturalesa a la societat i al cervell

Mihyun Kang, Zdenek Petrásek

• català

  La teoria dels grafs aleatoris tracta de les propietats asimptòtiques dels grafs dotats d’una determinada distribució de probabilitat; per exemple, estudia com evoluciona l’estructura de les components d’un graf aleatori uniforme a mesura que el nombre d’arestes augmenta. Des de l’inici de la teoria dels grafs aleatoris, formulada per Erd˝os i Rényi fa més de cinquanta anys, s’han introduït i estudiat diversos models de grafs aleatoris. Mentrestant la teoria de grafs s’ha anat obrint camí en altres ciències com una font molt rica de models per a descriure aspectes fonamentals d’un ventall molt ampli de fenòmens de gran complexitat. Aquest article és una introducció a la teoria dels grafs aleatoris i els seus progressos recents (amb èmfasi en la transició de fase i els fenòmens crítics, un tema favorit del primer autor) i a les aplicacions d’aquesta teoria.

  Es tracta d’una versió ampliada de l’article «Random graphs: from nature to society to the brain» [35] publicat al Seoul Intelligencer, un número especial del Math. Intelligencer, editat en ocasió del Congrés Internacional de Matemàtics que va tenir lloc a Seül l’any 2014.

• English

  The theory of random graphs deals with asymptotic properties of graphs equipped with a certain probability distribution; for example, it studies how the component structure of a uniform random graph evolves as the number of edges increases. Since the foundation of the theory of random graphs by Erd˝os and Rényi five decades ago, various random graph models have been introduced and studied. Graph theory has meanwhile found its way into other sciences as a rich source of models describing fundamental aspects of a broad range of complex phenomena. This article is a gentle introduction to the theory of random graphs and its recent developments (with focus on the phase transition and critical phenomena, a favourite topic of the first author) and applications.

  This is an extended version of the article entitled «Random graphs: from nature to society to the brain» [35] published in Seoul Intelligencer, a special issue of the Mathematical Intelligencer, on the occasion of International Congress of Mathematicians in Seoul in 2014.