기초과학연구원 이산수학그룹
The study of Hamiltonian graphs, i.e. finite graphs having a cycle that contains all vertices of the graph, is a central theme of finite graph theory. For infinite graphs such …
In this talk I will state a generalisation of the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of …
In combinatorics, Hopf algebras appear naturally when studying various classes of combinatorial objects, such as graphs, matroids, posets or symmetric functions. Given such a class of combinatorial objects, basic information …
In an n-vertex graph, there must be a clique or stable set of size at least $C\log n$, and there are graphs where this bound is attained. But if we look at …
An immersion of a graph H into a graph G sends edges of H into edge-disjoint trails of G. We say the immersion is flooding if every edge of G …
For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most …
A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic …
In the "cake partition" problem n players have each a list of preferred parts for any partition of the interval ("cake") into n sub-intervals. Woodall, Stromquist and Gale proved independently that under mild …
We prove a conjecture of Boros, Caro, Furedi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths, which is a restricted version of …
This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a …