Posts Tagged ‘AlexandrKostochka’

Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs

Monday, October 14th, 2019

IBS/KAIST Joint Discrete Math Seminar

Reconstructing graphs from smaller subgraphs
Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
2019/10/10 Thu 4:30PM-5:30PM
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 also show that all $3$-regular graphs are $2$-reconstructible.

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

Monday, October 14th, 2019

KAIST MathSci / IBS DIMAG Joint Colloquium

On Ramsey-type problems for paths and cycles in dense graphs
Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
2019/10/08 Tue 4:30PM-5:30PM
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 conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás, Ruszinkó, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp. This is joint work with Jozsef Balogh, Mikhail Lavrov and Xujun Liu.