Michał Seweryn, Dimension and standard examples in planar posets
The dimension of a poset is the least integer $d$ such that the poset is isomorphic to a subposet of the product of $d$ linear orders. In 1983, Kelly constructed …
10 events found.
Discrete Math Seminar
Events
-
-
Room B332 IBS (기초과학연구원)
-
-
Hyunwoo Lee (이현우), Reconstructing hypergraph matching polynomials
Room B332 IBS (기초과학연구원)By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all $n \geq k \geq 2$, one can reconstruct the matching polynomial …
-
Marcelo Garlet Milani, Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
Room B332 IBS (기초과학연구원)In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem. The theorem states the existence of a function f such that every digraph of directed tree-width f(k) contains a cylindrical …
-
Daniel McGinnis, A necessary and sufficient condition for $k$-transversals
Room B332 IBS (기초과학연구원)We solve a long-standing open problem posed by Goodman and Pollack in 1988 by establishing a necessary and sufficient condition for a finite family of convex sets in $\mathbb{R}^d$ to …
-
Nicola Lorenz, A Minor Characterisation of Normally Spanned Sets of Vertices
Room B332 IBS (기초과학연구원)A rooted spanning tree of a graph $G$ is called normal if the endvertices of all edges of $G$ are comparable in the tree order. It is well known that …
-
Marcin Briański, Burling Graphs as (almost) universal obstacles to $\chi$-boundedness
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 \(\chi\)-bounded …
-
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 $S$, a tournament is $S$-free if it has no subtournament isomorphic to $S$. Until now, there have been only a small number of tournaments $S$ such that …
-
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 …