***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Zixuan Xu (Princeton)

Thursday 1st October, 3:00 in Fine Hall 224.

Title: Improved lower bound on hypercube edge slicing

The n-dimensional hypercube is a well-studied combinatorial object across
many areas of mathematics and computer science. A hyperplane slices an edge
of the hypercube if it contains exactly one interior point of the edge. It
is natural to ask what is the minimum size of a hyperplane collection that
slices every edge of the hypercube. Motivated by applications in theoretical
computer science, this problem has attracted the attention of many
researchers over the past 50 years. We show that Omega(n^{13/19-o(1))
hyperplanes are required, improving on the previous results by O’Neil,
Yehuda—Yehudayoff, and Klein. We will discuss the main ideas that go into
proving these lower bounds and potentially some recent developments found by
GPT.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)