기초과학연구원 이산수학그룹
On June 27, 2022, Ben Lund from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on a large set of points with small radial projections in a vector space over a finite field. The title of his talk was “Radial projections in finite space“.
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 through $y$ and points of $E$. Clearly, $|\pi_y(E)|$ is at most the minimum of the number of lines through $y$ and $|E|$. I will discuss several results on the general question: For how many points $y$ can $|\pi_y(E)|$ be much smaller than this maximum?
This is motivated by an analogous question in fractal geometry. The Hausdorff dimension of a radial projection of a set $E$ in $n$ dimensional real space will typically be the minimum of $n-1$ and the Hausdorff dimension of $E$. Several recent papers by authors including Matilla, Orponen, Liu, Shmerikin, and Wang consider the question: How large can the set of points with small radial projections be? This body of work has several important applications, including recent progress on the Falconer distance conjecture.
This is joint with Thang Pham and Vu Thi Huong Thu.
On March 28, 2022, Ben Lund from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on the threshold function for a random subset of a finite vector space to have certain intersection properties with all m-dimensional affine subspaces at the Discrete Math Seminar. The title of his talk was “Thresholds for incidence properties in finite vector spaces“.
Suppose that $E$ is a subset of $\mathbb{F}_q^n$, so that each point is contained in $E$ with probability $\theta$, independently of all other points. Then, what is the probability that there is an $m$-dimensional affine subspace that contains at least $\ell$ points of $E$? What is the probability that $E$ intersects all $m$-dimensional affine subspaces? We give Erdős-Renyi threshold functions for these properties, in some cases sharp thresholds. Our results improve previous work of Chen and Greenhill. This is joint work with Jeong Han Kim, Thang Pham, and Semin Yoo.
A family $\mathcal F$ of subsets of {1,2,…,n} is called maximal k-wise intersecting if every collection of at most k members from $\mathcal F$ has a common element, and moreover, no set can be added to $\mathcal F$ while preserving this property. In 1974, Erdős and Kleitman asked for the smallest possible size of a maximal k-wise intersecting family, for k≥3. We resolve this problem for k=3 and n even and sufficiently large.
This is joint work with Kevin Hendrey, Casey Tompkins, and Tuan Tran.
On November 2, 2021, Ben Lund from IBS Discrete Mathematics Group gave a talk on the smallest possible size of a maximal 3-wise intersecting family of subsets of {1,2,…,n} for large n, answering a problem of Erdős and Kleitman proposed in 1974. The title of his talk was “Maximal 3-wise intersecting families“.
On May 25, 2021, Ben Lund from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on the existence of a limit shape for lattice zonotopes in all dimensions and other relevant results. The title of his talk was “Limit shape of lattice Zonotopes”.
A convex lattice polytope is the convex hull of a set of integral points. Vershik conjectured the existence of a limit shape for random convex lattice polygons, and three proofs of this conjecture were given in the 1990s by Bárány, by Vershik, and by Sinai. To state this old result more precisely, there is a convex curve $L \subset [0,1]^2$ such that the following holds. Let $P$ be a convex lattice polygon chosen uniformly at random from the set of convex lattice polygons with vertices in $[0,N]^2$. Then, for $N$ sufficiently large, $(1/N)P$ will be arbitrarily close (in Hausdorff distance) to $L$ with high probability. It is an open question whether there exists a limit shape for three dimensional polyhedra.
I will discuss this problem and some relatives, as well as joint work with Bárány and Bureaux on the existence of a limit shape for lattice zonotopes in all dimensions.
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.