Ben Lund, Furstenberg sets over finite fields
An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved …
10 events found.
Discrete Math Seminar
Events
-
-
Room B232 IBS (기초과학연구원)
-
Adam Zsolt Wagner, The largest projective cube-free subsets of $Z_{2^n}$
Room B232 IBS (기초과학연구원)What is the largest subset of $Z_{2^n}$ that doesn't contain a projective d-cube? In the Boolean lattice, Sperner's, Erdos's, Kleitman's and Samotij's theorems state that families that do not contain …
-
Dillon Mayhew, Courcelle’s Theorem for hypergraphs
Room B232 IBS (기초과학연구원)Courcelle's Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed …
-
-
Dong Yeap Kang (강동엽), Fragile minor-monotone parameters under random edge perturbation
Room B232 IBS (기초과학연구원)We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, …
-
Xin Zhang (张欣), On the equitable tree-coloring of graphs with low degeneracy
Room B232 IBS (기초과학연구원)A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest, and is equitable if the sizes of any two color classes differ by …
-
-
Eun-Kyung Cho (조은경), Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$
Room B232 IBS (기초과학연구원)Given a graph $G$, a decomposition of $G$ is a collection of spanning subgraphs $H_1, \ldots, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ …
-
Dabeen Lee (이다빈), On a generalization of the Chvátal-Gomory closure
Room B232 IBS (기초과학연구원)Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called …
-
Kevin Hendrey, Covering radius in the Hamming permutation space
Room B232 IBS (기초과학연구원)Our problem can be described in terms of a two player game, played with the set $\mathcal{S}_n$ of permutations on $\{1,2,\dots,n\}$. First, Player 1 selects a subset $S$ of $\mathcal{S}_n$ and shows …
-
Ringi Kim (김린기), The strong clique number of graphs with forbidden cycles
Room B232 IBS (기초과학연구원)The strong clique number of a graph $G$ is the maximum size of a set of edges of which every pair has distance at most two. In this talk, we …
-
-
Pascal Gollin, Disjoint dijoins for classes of dibonds in finite and infinite digraphs
Room B232 IBS (기초과학연구원)A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A …