**I am excited to announce the official start of our new Discrete Geometry group!**This event will also be the first meeting of the NYC Geometry Seminar in the CUNY Graduate Center (midtown Manhattan). It will take place at 2pm of Friday August 31st. If you are in the NYC area and interested in Discrete Geometry and related topics – come join us!

# Linear Algebra Riddle

**Riddle.**A library has books and subscribers. Each subscriber read at least one book from the library. Prove that there must exist two

*disjoint*sets of subscribers who read exactly the same books (that is, the union of the books read by the subscribers in each set is the same).

**Very**basic linear algebra. Try the first thing that comes to mind.

# Discrete Geometry Classic: Two-distance Sets

**Warm-up problem.**What is the maximum size of a set such that the distance between every two points of the set is 1?

**The two-distance sets problem.**A point set is a

*two-distance set*if there exist such that the distance between every pair of points of is either or . What is the maximum size of a two-distance set in ?

**Theorem.**

*Every two-distance set in has size at most .*

**Proof.**Let be a two-distance set in , and denote the two distances as . Given points , we denote the distance between them as . We refer to a point in as . For , define the polynomial as

# The Math Art of Gábor Damásdi

*Gábor Damásdi.*

# Points in General Position

*general position*. Most commonly, this definition refers to point sets with no three collinear points and no four cocircular points (that is, no circle contains four points of the set). A few examples of such problems:

- What is the minimum number of distinct distances that are spanned by a set of points in general position?
- What is the minimum number of convex -gons determined by points in general position?
- For even , what is the maximum number of distinct ways in which one can cut a set of points in general position by a line into two halves, each of cardinality ?
- What is the maximum number of points that can be placed on an grid so that no three points are collinear. What happens when we also forbid four cocircular points?

**Construction 1: Subsets of the integer lattice.**Our first construction involves finding a large subset of an section of the integer lattice that is in general position. The basic idea for this construction seems to originate from Erdős (for example, see this paper of Roth), although we will follow a later variant of Thiele.

*An example of the first construction, created by Gábor Damásdi.*

- Erdős and Purdy asked for the size of the largest subset of the integer lattice with no three points on a line and no four on a circle. The above construction provides the current best lower bound for this problem.
- Erdős, Hickerson, and Pach asked whether there exists a planar set of points in general position that spans no parallelograms and still determines distinct distances. Dumitrescu provided a positive answer to this question by using the above construction.
- The
*Heilbronn triangle problem*asks for the smallest such that every set of points in the unit square determine a triangle of area at most . Erdős used a variant of the above construction to produce one of the first non-trivial lower bounds for the problem.

**Construction 2: Projection from a hypersphere.**In our first construction, the point set has some structure since it is a subset of a section of the integer lattice. The structure in our second construction also originates from a lattice, although in a very different way. This construction comes from a paper of Erdős, Füredi, Pach, and Ruzsa, and seems to be influenced by earlier ideas of Behrend.

*every*plane would remain collinear. This is why we take the points of to be on the hypersphere : Since every line intersects the hypersphere in at most two points, no three points of are collinear.

# Child Care at STOC 2018 + Riddle

We are pleased to announce that we will provide pooled, subsidized

child care at STOC 2018. The cost will be $40 per day per child for

regular conference attendees, and $20 per day per child for students.

For more detailed information, including how to register for STOC 2018

childcare, see http://acm-stoc.org/stoc2018/childcare.html

# Research and Willpower and Fools

“The way to get to the top of the heap in terms of developing original research is to be a fool, because only fools keep trying. You have idea number 1, you get excited, and it flops. Then you have idea number 2, you get excited, and it flops. Then you have idea number 99, you get excited, and it flops. Only a fool would be excited by the 100th idea, but it might take 100 ideas before one really pays off. Unless you’re foolish enough to be continually excited, you won’t have the motivation, you won’t have the energy to carry it through. God rewards fools.”

*Martin Hellman*