Alexandr V. Kostochka, On Ramsey-type problems for paths and cycles in dense graphs
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 …
10 events found.
Seminars and Colloquiums
Events
-
-
Room 1501, Bldg. E6-1, KAIST
-
Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs
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 …
-
Zi-Xia Song (宋梓霞), Ramsey numbers of cycles under Gallai colorings
Room B232 IBS (기초과학연구원)For a graph $H$ and an integer $k\ge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ …
-
Joonkyung Lee (이준경), On some properties of graph norms
Room B232 IBS (기초과학연구원)For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $p\geq e(H)$, denoted by $t_H(W)$. One may then define …
-
Pascal Gollin, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs
Room B232 IBS (기초과학연구원)Given a cardinal $\lambda$, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$, and a $\lambda$-covering of $G$ is a family of spanning …
-
-
Sun Kim (김선), Two identities in Ramanujan’s Lost Notebook with Bessel function series
Room 1401, Bldg. E6-1, KAISTOn page 335 in his lost notebook, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities …
-
Tony Huynh, Stable sets in graphs with bounded odd cycle packing number
Room B232 IBS (기초과학연구원)It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it …
-
Ruth Luo, Induced Turán problems for hypergraphs
Room B232 IBS (기초과학연구원)Let $F$ be a graph. We say that a hypergraph $\mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the …
-
Frédéric Meunier, Topological bounds for graph representations over any field
Room B232 IBS (기초과학연구원)Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb …
-
-
Jakub Gajarský, First-order interpretations of bounded expansion classes
Room B232 IBS (기초과학연구원)The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter …