IBS/KAIST Joint Discrete Math Seminar

TU Graz

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

IBS/KAIST Joint Discrete Math Seminar

The genus of a random graph and the fragile genus property

Mihyun Kang (강미현)

TU Graz

TU Graz

2019/08/20 Tue 4:30PM-5:30PM

In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges can increase the genus of a randomly perturbed graph. (Joint work with Chris Dowden and Michael Krivelevich)

Phase transitions in random graphs

Mihyun Kang (강미현)

Institut für Mathematik, Freie Universität Berlin, Germany

Institut für Mathematik, Freie Universität Berlin, Germany

2011/09/30 Fri 4PM-5PM

The phase transition deals with sudden global changes and is observed in many fundamental problems from statistical physics, mathematics and theoretical computer science, for example, Potts models, graph colourings and random k-SAT. The phase transition in random graphs refers to a phenomenon that there is a critical edge density, to which adding a small amount a drastic change in the size of the largest component occurs. In Erdös-Renyi random graph, which begins with an empty graph on n vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches n/2 and a giant component emerges. Since this seminal work of Erdös and Renyi, various random graph models have been introduced and studied. In this talk we discuss phase transitions in several random graph models, including Erdös-Renyi random graph, random graphs with a given degree sequence, random graph processes and random planar graphs.

Enumeration and uniform sampling of planar structures

Mihyun Kang (강미현)

Institut für Informatik, Humboldt-Universität zu Berlin, Berlin, Germany.

Institut für Informatik, Humboldt-Universität zu Berlin, Berlin, Germany.

2008/03/20 Thu, 3PM-4PM

Planar structures, particularly planar graphs, have attracted much attention during the last few years, from the viewpoints of enumeration, sampling, and typical properties. In order to determine the number of graphs of interest, typically graphs are decomposed according to connectivity. Using the decomposition tree we derive recursive counting formulas, from which we can design a uniform sampling algorithm to sample a random instance. Furthermore, we interpret the decomposition in terms of equations of generating functions, from which we can estimate the asymptotic numbers using singularity analysis.

On the other hand, the matrix integral method, a technique of theoretical physics, employs the traces of Hermitian matrices to express the number of embedded graphs on a 2-dimensional surface and planar maps in particular. This leads to the map enumeration results analogous to those obtained by combinatorial methods. A natural question is whether the method may as well be applied to the enumeration of graphs embeddable on a 2-dimensional surface. This can be done by applying the matrix integral to combinatorially defined functions, in order to loosen the strong connection between maps and the traces.

In this talk I will discuss recent results on this subject.