Nicola Lorenz, A Minor Characterisation of Normally Spanned Sets of Vertices
Room B332 IBS (기초과학연구원)A rooted spanning tree of a graph
10 events found.
Discrete Math Seminar
Marcin Briański, Burling Graphs as (almost) universal obstacles to
Room B332
IBS (기초과학연구원)
What causes a graph to have high chromatic number? One obvious reason is containing a large clique (a set of pairwise adjacent vertices). This naturally leads to investigation of
Pascal Schweitzer, Recent insights surrounding combinatorial approaches to isomorphism and symmetry problems
Room B332 IBS (기초과학연구원)Modern practical software libraries that are designed for isomorphism tests and symmetry computation rely on combinatorial techniques combined with techniques from algorithmic group theory. The Weisfeiler-Leman algorithm is such a …
Eunjin Oh (오은진), Approximation Algorithms for the Geometric Multimatching Problem
Room B332 IBS (기초과학연구원)Let S and T be two sets of points in a metric space with a total of n points. Each point in S and T has an associated value that specifies an upper limit on how many points it can …
Seokbeom Kim (김석범), The structure of △(1, 2, 2)-free tournaments
Room B332 IBS (기초과학연구원)Given a tournament
Meike Hatzel, Counterexample to Babai’s lonely colour conjecture
Room B332 IBS (기초과학연구원)Motivated by colouring minimal Cayley graphs, in 1978 Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by constructing graphs of arbitrarily large …
Denys Bulavka, Strict Erdős-Ko-Rado Theorems for Simplicial Complexes
Room B332 IBS (기초과학연구원)The now classical theorem of Erdős, Ko and Rado establishes the size of a maximal uniform family of pairwise-intersecting sets as well as a characterization of the families attaining such …
On-Hei Solomon Lo, Minors of non-hamiltonian graphs
Room B332 IBS (기초과학연구원)A seminal result of Tutte asserts that every 4-connected planar graph is hamiltonian. By Wagner's theorem, Tutte's result can be restated as: every 4-connected graph with no
Attila Jung, The Quantitative Fractional Helly Theorem
Room B332 IBS (기초과학연구원)Two celebrated extensions of Helly's theorem are the Fractional Helly theorem of Katchalski and Liu (1979) and the Quantitative Volume theorem of Barany, Katchalski, and Pach (1982). Improving on several …