Peter Nelson, Formalizing matroid theory in a proof assistant
For the past few years, I've been working on formalizing proofs in matroid theory using the Lean proof assistant. This has led me to many interesting and unexpected places. I'll …
10 events found.
Discrete Math Seminar
Events
-
-
Room B332 IBS (기초과학연구원)
-
Dillon Mayhew, Monadic second-order definability for gain-graphic matroids
Room B332 IBS (기초과학연구원)Every (finite) matroid consists of a (finite) set called the ground set, and a collection of distinguished subsets called the independent sets. A classic example arises when the ground set …
-
-
Amadeus Reinald, Oriented trees in $O(k \sqrt{k})$-chromatic digraphs, a subquadratic bound for Burr’s conjecture
Room B332 IBS (기초과학연구원)In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which …
-
Neal Bushaw, Edge-colored Extremal Problems
Room B332 IBS (기초과학연구원)An edge-colored graph $H$ is called rainbow if all of its edges are given distinct colors. An edge-colored graph $G$ is then called rainbow $H$-free when no copy of $H$ in …
-
Zhihan Jin (金之涵), The Helly number of Hamming balls and related problems
Room B332 IBS (기초과학연구원)We prove the following variant of Helly’s classical theorem for Hamming balls with a bounded radius. For $n > t$ and any (finite or infinite) set $X$, if in a …
-
Gábor Tardos, Extremal theory of 0-1 matrices
Room B332 IBS (기초과학연구원)We say that a 0-1 matrix A contains another such matrix (pattern) P if P can be obtained from a submatrix of A by possibly changing a few 1 entries …
-
-
Mathias Schacht, Canonical colourings in random graphs
Room B332 IBS (기초과학연구원)Rödl and Ruciński established Ramsey's theorem for random graphs. In particular, for fixed integers $r$, $\ell\geq 2$ they showed that $n^{-\frac{2}{\ell+1}}$ is a threshold for the Ramsey property that every …
-
Kyeongsik Nam (남경식), Random walks on percolation
Room B332 IBS (기초과학연구원)In general, random walks on fractal graphs are expected to exhibit anomalous behaviors, for example heat kernel is significantly different from that in the case of lattices. Alexander and Orbach …
-
Colin Geniet, Permutations, patterns, and twin-width
Room B332 IBS (기초과학연구원)This talk will first introduce combinatorics on permutations and patterns, presenting the basic notions and some fundamental results: the Marcus-Tardos theorem which bounds the density of matrices avoiding a given …
-
Felix Christian Clemen, Triangles in the Plane
Room B332 IBS (기초과학연구원)A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of $n$ points in the plane. Since …