Younjin Kim (김연진), On the extremal problems related to Szemerédi’s theorem
In 1975, Szemerédi proved that for every real number $\delta > 0 $ and every positive integer $k$, there exists a positive integer $N$ such that every subset $A$ of …
10 events found.
Discrete Math Seminar
Events
-
-
Room B232 IBS (기초과학연구원)
-
Boram Park (박보람), Odd coloring of sparse graphs
Room B232 IBS (기초과학연구원)We introduce an odd coloring of a graph, which was introduced very recently, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to …
-
-
Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems
Room B332 IBS (기초과학연구원)In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if …
-
Kyeongsik Nam (남경식), Large deviations for subgraph counts in random graphs
Room B332 IBS (기초과학연구원)The upper tail problem for subgraph counts in the Erdos-Renyi graph, introduced by Janson-Ruciński, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph …
-
Andreas Holmsen, A colorful version of the Goodman-Pollack-Wenger transversal theorem
Room B332 IBS (기초과학연구원)Hadwiger's transversal theorem gives necessary and sufficient conditions for the existence of a line transversal to a family of pairwise disjoint convex sets in the plane. These conditions were subsequently …
-
Stijn Cambie, The precise diameter of reconfiguration graphs
Room B332 IBS (기초과학연구원)Reconfiguration is about changing instances in small steps. For example, one can perform certain moves on a Rubik's cube, each of them changing its configuration a bit. In this case, …
-
Hongseok Yang (양홍석), Learning Symmetric Rules with SATNet
Room B332 IBS (기초과학연구원)SATNet is a differentiable constraint solver with a custom backpropagation algorithm, which can be used as a layer in a deep-learning system. It is a promising proposal for bridging deep …
-
-
Amadeus Reinald, Twin-width and forbidden subdivisions
Room B332 IBS (기초과학연구원)Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, problems expressible in FO logic can be solved in FPT time when provided …
-
Ben Lund, Radial projections in finite space
Room B332 IBS (기초과학연구원)Given a set $E$ and a point $y$ in a vector space over a finite field, the radial projection $\pi_y(E)$ of $E$ from $y$ is the set of lines that …
-
-
Eric Vigoda, Computational phase transition and MCMC algorithms
Room B332 IBS (기초과학연구원)This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to …