기초과학연구원 이산수학그룹
On January 19, 2021, Ben Lund from the IBS Discrete Mathematics Group presented his result with Matija Bucic, Pat Devlin, Mo Hendon, and Dru Horne showing that each perfect matching in a bipartite graph intersects at least half of all perfect matchings. The title of his talk was “Perfect matchings and derangements on graphs“.
We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G. This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph, and in terms of derangements and permutations on graphs. We give several related results and open questions. This is joint work with Matija Bucic, Pat Devlin, Mo Hendon, and Dru Horne.
On August 25, 2020, Ben Lund from IBS Discrete Mathematics Group presented a talk on his generalization of Beck’s theorem resulting lower bounds on the number of planes spanned by a set of points and its various applications. The title of his talk was “Point-plane incidence bounds“.
The IBS discrete mathematics group welcomes Dr. Ben Lund and Dr. Tuan Tran, new research fellows at the IBS discrete mathematics group from August 1, 2020.
Ben Lund received his Ph.D. from the Department of Mathematics at Rutgers University in 2017 under the supervision of Prof. Shubhangi Saraf. Before joining the IBS, he was a postdoc at Princeton University and a postdoc at the University of Georgia.
Tuan Tran received his Ph.D. from the Department of Mathematics at the Freie Universität Berlin in 2015 under the supervision of Prof. Tibor Szabó. Before joining the IBS, he was a lecturer at Hanoi University of Science and Technology, a postdoc at ETH Zürich, and a postdoc at Czech Academy of Sciences. He won the IBS Young Scientist Fellowship.
In the early 1980s, Beck proved that, if P is a set of n points in the real plane, and no more than g points of P lie on any single line, then there are $\Omega(n(n-g))$ lines that each contain at least 2 points of P. In 2016, I found a generalization of this theorem, giving a similar lower bound on the number of planes spanned by a set of points in real space. I will discuss this result, along with a number of applications and related open problems.
On January 15, 2020, Ben Lund from Princeton University gave a talk about a generalization of the Kakeya conjecture posed by Ellenberg, Oberlin, and Tao. The title of his talk was “Furstenberg sets over finite fields“. He is visiting the IBS discrete mathematics group until January 21, Tuesday.
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 by Dvir in 2008. Dvir’s proof introduced the polynomial method to incidence geometry, which led to the solution to many long-standing problems in the area.
I will talk about a generalization of the Kakeya conjecture posed by Ellenberg, Oberlin, and Tao. A $(k,m)$-Furstenberg set S in $\mathbb F_q^n$ has the property that, parallel to every affine $k$-plane V, there is a k-plane W such that $|W \cap S| > m$. Using sophisticated ideas from algebraic geometry, Ellenberg and Erman showed that if S is a $(k,m)$-Furstenberg set, then $|S| > c m^{n/k}$, for a constant c depending on n and k. In recent joint work with Manik Dhar and Zeev Dvir, we give simpler proofs of stronger bounds. For example, if $m>2^{n+7}q$, then $|S|=(1-o(1))mq^{n-k}$, which is tight up to the $o(1)$ term.