Loading Events

Upcoming Events › Discrete Math Seminar

Events Search and Views Navigation

Event Views Navigation

August 2019

:

Mihyun Kang (강미현), The genus of a random graph and the fragile genus property

August 20 Tuesday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

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)

Find out more »

October 2019

:

Alexandr V. Kostochka, On Ramsey-type problems for paths and cycles in dense graphs

Speaker

Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
https://faculty.math.illinois.edu/~kostochk/
October 8 Tuesday @ 4:30 PM - 5:30 PM
Room 1501, Bldg. E6-1, KAIST

A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors, there is a monochromatic copy of $H$. In these terms, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$. We consider sufficient…

Find out more »
:

Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs

Speaker

Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
https://faculty.math.illinois.edu/~kostochk/
October 10 Thursday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

A graph or graph property is $\ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $\ell$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each $\ell\in\mathbb N$, there is an integer $n=n(\ell)$ such that every graph with at least $n$ vertices is $\ell$-reconstructible. We show that for each $n\ge7$ and every $n$-vertex graph $G$, the degree list and connectedness of $G$ are $3$-reconstructible, and the threshold $n\geq 7$ is sharp for both properties.‌ We…

Find out more »
+ Export Events