Combinatorial Journals are Changing

I used to ask most combinatorialists I met for their opinion about the level of various journals. With this feedback, I compiled a rough journal ranking for combinatorics papers (for personal use). This was a very educational experience for me as a new combinatorialist. I learned that different people have rather different opinions. For example, people tend to have a higher opinion of the journals of their own combinatorial sub-field.

However, people’s opinions did not vary much with respect to the very few top combinatorics journals. In particular, I don’t recall a single person who didn’t agree with Journal of Combinatorial Theory Series A being one of those (and similarly Combinatorica). This makes the following announcement quite significant:

“The majority of the JCT A editorial boards have recently notified Elsevier that they will not be renewing their contracts, and will resign after December 2020”

(Thank you Pablo Soberón for telling me about this.) The reason for this development is JCTA belonging to Elsevier. A new substitute journal has been created: Combinatorial Theory. This journal is “mathematician-owned, and fully open access, with no charges for authors or readers.” It already has a very impressive editorial board.

It would be interesting to see what happens next. So far not a lot of information can be found online. Are any combinatorialists plan to stand by JCTA? What about Elsevier’s top graph theory journal: Journal of Combinatorial Theory Series B?

There is one thing I really like about JCTA, and very much hope that Combinatorial Theory would adopt. Out of the stronger combinatorics journals, JCTA seems to be the one most open to all different types of combinatorics. From what I hear and see, all others tend to be at least somewhat biased towards some sub-fields. I’m told that JCTA originally focused on enumerative combinatorics, but this seems to be far from the case in recent years.

If you have more information about these developments, I would be very happy to hear!

Mathematics for Human Flourishing

I read a lot of “popular math” books. I also wrote about some in past posts. But I’ve never read a book similar to Mathematics for Human Flourishing by Francis Su. I already knew the math presented in this book and almost all other topics covered. I even knew some of Su’s personal stories from his past writings. But somehow that did not matter. I got more out of this book than from many other books whose topics were completely new to me.

So what is this unusual book about? Quoting from the first paragraph:

… this is a book that grounds mathematics in what it means to be a human being and to live a more fully human life.

Different people are likely to describe the main topic of the book in different ways. One might be “How one can live a healthy and fulfilling life in mathematics.” Another might be “How to do good in the world through mathematics (and not by solving a millennium prize problem).” There are likely to be many other different descriptions. But hopefully you get a vague idea.

To emphasize his main ideas, Su includes several “subplots” that develop throughout the book. One subplot is Su’s relationship with Christopher Jackson. Jackson is serving a 32-year prison sentence for a string of armed robberies. While in prison, he started reading basic math books, gradually moving to more advanced topics (under Su’s guidance). The correspondence between Jackson and Su exposes a fascinating story of how one finds their place in the world through math.

Another subplot is Su’s personal life. Su shares highly personal stories. Some stories are about his struggles with math and others unrelated to math. At least once I was so shocked by what Su was sharing that I had to stop reading for a few minutes.

A large portion of the book describes the mathematical world to people who are unfamiliar with it. This starts with the basic step of explaining that math is not about plugging numbers into formulas. It develops all the way to advanced topics such as how mentoring works. Su does excellent work explaining these ideas to non-mathematicians, in a fun and clear way. When describing ideas such as searching for patterns, real mathematical examples are provided. I would definitely recommend this book to family and non-math friends who wish to know more about what I do.

I would also recommend this book to students. While discussing how the math world works, it raises various issues that cause anxiety and distance people away from math. When working with students, I am going to steal some sentences, such as

“A popular myth of doing math is that either you see the answer or you don’t. In reality, you demonstrate mathematical power by assembling possible strategies and trying them to see if they will work.”

Since I know how the math world works, the mathematics explained in the book, and even some of Su’s personal stories, how could I get much out of this book? It got me to think about what exactly I like in math and in my work. It helped me see more clearly what my future goals are. It got me to think about how to better handle various tricky interactions with students and mentees. And more. I cannot say that about many books.

If your goal is to learn more math, do not read this book. If you are cynical about topics such as getting students less anxious about math, do not read this book. Read it if you are a mathematician who wants to rethink your attitude towards math and teaching. Or to get others more excited about math. Read it if you are a student who might have some anxiety about math or just want to know more about the math world. Recommend it to non-mathematicians who want to know what you are doing with your life.

Mind-Benders for the Quarantined

Peter Winkler is a world expert on mathematical puzzles (he is also an excellent researcher and this year’s resident mathematician of the MoMath). I just learned about two things that he is currently up to.

Winkler is running Mind-Benders for the Quarantined. After signing up to this free service, you receive a mathematical puzzle every Sunday, by email. You then get a subtle hint on Tuesday, a big hint on Thursday, and the solution on Saturday.

dartmouth-news-peter-winkler-810_455_0

Winkler’s new book should be out around the end of 2020. While he already published wonderful book collections of mathematical puzzles in the past, this one is meant to be a special collection of the world’s top puzzles. For example, the new book would also include the best puzzles from Winkler’s past books.

Polymath REU

I am excited to announce a new program for undergraduates: The Polymath REU will run during the summer of 2020.

Due to the pandemic, many students are stuck at home without a summer program. The aim of the Polymath REU program is to provide research opportunities for such students. The program consists of research projects in a variety of mathematical topics and runs in the spirit of the Polymath Project. Each research project is mentored by an active researcher with experience in undergraduate mentoring.


My collaborators in the program are Ben Brubaker, Steven Miller, and Yunus Zeytuncu. I like this group! Each person has experience with running an REU program and together we cover a variety of mathematical fields.

The program is open to all undergraduate students, with no nationality or geographic restrictions. Acceptance is not automatic. However, the program is open to the majority of undergraduates having experience with writing mathematical proofs.

The research part of the program begins June 22nd and ends August 15th. The applications deadline is June 10th. For more information, see our website.

If you can, please help us spread the word. We would love to reach many undergraduates who are stuck at home this summer.

help-spread-the-word-300x135

Math Summer Programs

The virus is causing some math summer programs to cancel. Surprisingly, this led to something wonderful. Unusually strong undergrads are starting to run their own online summer math programs for high school students.

1. The MORPH program is run by the Harvard math club. It offers a variety of mathematical topics at different levels of difficulty. It is not only free, but also subsidizes books for admitted students.

2. Alec Sun’s program seems to be more focused towards research.

I know students from the staff of both programs and believe that (math-wise) they are some of the strongest in the country.

(As usual, high-school students who wish to do a research project are also welcome to contact me. Unlike the above, this is not for a summer project. This is for students who wish to spend a large amount of time spread over a many months, with the goal of producing their own research paper. See more here.)

summerPD-600x400

New Horizons in Geometry and Micha Sharir

Always wanted to visit Israel? Like discrete or computational geometry, and Micha Sharir? Considering what to do with this year’s travel funds? Join us in Tel Aviv!

https://geometrynyc.wixsite.com/sharir (Open on a computer – does not support mobile yet.) If you can, please help us spread the word.

Micha

Partial list of speakers:

  • Pankaj Agarwal (Duke)
  • Noga Alon (Princeton)
  • Boris Aronov (NYU)
  • Shiri Artstein-Avidan (Tel Aviv University)
  • Kenneth Clarkson (IBM Almaden Research center)
  • Herbert Edelsbrunner (IST Austria)
  • Esther Ezra (Bar Ilan University)
  • Leonidas Guibas (Stanford)
  • Dan Halperin (Tel Aviv University)
  • Sariel Har-Peled (University of Illinois at Urbana–Champaign)
  • Gil Kalai (Hebrew University of Jerusalem)
  • Haim Kaplan (Tel Aviv University)
  • Nets Katz (Caltech)
  • Matya Katz (Ben Gurion University)
  • Klara Kedem (Ben Gurion University)
  • Nati Linial (Hebrew University of Jerusalem)
  • Janos Pach (Alfréd Rényi Institute of Mathematics)
  • József Solymosi (UBC)
  • Emo Welzl (ETH Zurich)

The conference is organized by Orit Raz, Natan Rubin, and myself. But the nice list of speakers is not due to us – Micha has a lot of impressive friends!

For any questions about the conference, feel free to contact me.

Updates

I did not post anything for almost five months – life has been very busy lately! I hope to get back to posting regularly relatively soon. In the meantime, I wanted to at least have a brief updates post.

I just made a revision of my book about incidences and polynomial methods. Joshua Zahl and I have been running a polynomial methods summer school for graduate students, at MSRI. This led to several topics being added to the book, such as a proof of the cap set theorem and a sum-product bound over finite fields. I also added many exercises, with a focus on clever elegant problems whose solution is not too technical. Many of those exercise have been carefully checked by the participants of the summer school 🙂

MSRI

If you’d like to see more from the summer school, you can now watch close to 25 hours of Joshua Zahl and myself talking about polynomial methods. Starting here. We were lucky to have Marina Iliopoulou and Cosmin Pohoata helping us run this program. And also lucky to have a group of impressive graduate students participating and solving all of our weird exercise!

Our REU program for this summer is getting close to its end. I am amazed by the amount of strong results this summer’s participants produced. Once some of these results will become available online, this would be a good topic for a separate post.

IMG-0217.JPG

I plan to soon write about several interesting events that we will be holding this academic year, upcoming hiring, and other news. I just need some time!

The Baruch Distinguished Mathematics Lecture Series

I am happy to announce the beginning of the Baruch Distinguished Mathematics Lecture Series. In this series we will bring established mathematicians to give talks to a general mathematical audience.

Our first Distinguished Lecture, by Bjorn Poonen, will be “Undecidability in Number Theory”. Click here for the full details. The talk is open to everyone, and includes refreshments. After the talk we will also go to lunch with the speaker.

dls

NYC Discrete Geometry: Introductory Meeting

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!

The introductory meeting would not consist of the standard seminar presentation. Instead, the purpose of the event is to meet people who are interested in Discrete Geometry, Computational Geometry, and so on (with people coming from NYU, Princeton, various CUNYs, etc). Participants will introduce themselves to the audience and mention the main topics that interest them. You are welcome to either introduce yourself, or just to come listen and have some pastries. If you introduce yourself, you are encouraged to briefly state a major open problem you wish you could solve.

For the exact location, see the event page. Personally, I plan to have more technical math discussions with some participants before and after this meeting.

Opening

Difference Sets with Local Properties

I recently attended a wonderful workshop about Algebraic methods in combinatorics, which took place in Harvard’s CMSA. There were many interesting participants from a variety of combinatorial fields, and a very friendly/productive atmosphere. My talk focused on a recent work with Cosmin Pohoata, and I also mentioned some distinct distances result that we derived. During the talk Zeev Dvir asked about an additive variant of the problem. After thinking about this variant for a bit, I think that it is a natural interesting problem. Surprisingly, so far I did not manage to find any hint of previous work on it (this might say more about my search capabilities than about the problem…)

zeevCosmin
Zeev Dvir and Cosmin Pohoata.

Let \phi(n,k,\ell)  denote the minimum size A-A  can have, when A  is a set of n  real numbers with the property that for any A' \subset A  with |A'|=k  we have |A'-A'|\ge \ell  . That is, by having a local additive property of every small subset, we wish to obtain a global additive property of the entire set. For simplicity, we will ignore zero in the difference set. Similarly, we will ignore negative differences. These assumptions do not change the problem, but make it easier to discuss.

As a first example, note that \phi(n,3,3)  is the minimum number of differences determined by a set of n  reals with no 3-term arithmetic progressions. Behrend’s construction is a set A  of positive integers a_1< a_2 < \cdots < a_n  with no 3-term arithmetic progression and a_n < n2^{O(\sqrt{\log n})}  . Thus, \phi(n,3,3) < n2^{O(\sqrt{\log n})}  .

For another simple example, Consider a constant k\ge 4  . Since we consider only positive differences, any set of k  reals determines at most \binom{k}{2}  differences. If a specific difference d  repeats \lfloor k/2 \rfloor  times, then by taking the numbers that span d  we obtain A'\subset A  such that |A'|\le k  and |A'-A'| \le \binom{k}{2}- \lfloor k/2 \rfloor+1  . Thus, by asking every subset of size k  to span at least \binom{k}{2}- \lfloor k/2 \rfloor+2  differences, we obtain that no difference repeats \lfloor k/2 \rfloor  times in A  . In other words

\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2 \right) = \Omega\left(n^2\right).

Repeating a simple argument of Erdős and Gyárfás gives

\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +1\right) = \Omega\left(n^{4/3}\right).

That is, when moving from \ell = \binom{k}{2}-\lfloor k/2 \rfloor +2  to \ell = \binom{k}{2}-\lfloor k/2 \rfloor +1  , we move from a trivial problem to a wide open one. My work with Cosmin Pohoata leads to the following result.

Theorem 1. For any d\ge 2  there exists c  such that

\phi\left(n,k,\binom{k}{2}-k\frac{d}{d+1}+c\right) =\Omega\left(n^{1+1/d} \right).

For example, when d=2  we get the bound

\phi\left(n,k,\binom{k}{2}-\frac{2k}{3}+c\right) =\Omega\left(n^{3/2} \right).

When d=3  we get a significant improvement for the range of the Erdős-Gyárfás bound:

\phi\left(n,k,\binom{k}{2}-\frac{2k}{3}+c\right) =\Omega\left(n^{3/2} \right). \qquad \qquad \qquad (1)

Since not much is known for this problem, it seems plausible that additional bounds could be obtained using current tools. Our technique does not rely on any additive properties, and holds for a more abstract scenario of graphs with colored edges. Hopefully in the case of difference sets one would be able to use additive properties to improve the bounds. Moreover, so far I know nothing about much smaller values of \ell  , such as \phi(n,k,100k)  .

Proof sketch for Theorem 1. For simplicity, let us consider the case of d=3  , as stated in (1)  . Other values of d  are handled in a similar manner. Let A  be a set of n  reals, such that any A'\subset A  of size k  satisfies |A'-A'|\ge \binom{k}{2}-\frac{3k}{4}+13  . We define the third distance energy of A  as

E_3(A) = \left|\left\{(a_1,a_2,a_3,b_1,b_2,b_3) \in A^6 :\, a_1-b_1=a_2-b_2=a_3-b_3 >0 \right\}\right|.

The proof is based on double counting E_3(A)  . For \delta\in {\mathbb R}  , let m_\delta = \left|\left\{(a,b)\in A^2 : a-b = \delta\right\}\right|  . That is, m_\delta  is the number of representations of \delta  as a difference of two elements of A  . Note that the number of 6-tuples that satisfy a_1-b_1=a_2-b_2=a_3-b_3  is m_\delta^3  . A simple application of Hölder ‘s inequality implies

E_3(A) = \sum_{\delta>0} m_\delta^3 \ge \frac{n^6}{|A-A|^2}.

To obtain a lower bound for |A-A|  , it remains to derive an upper bound for E_3(A)  .

For j\in {\mathbb N}  let k_j  denote the number of differences \delta \in {\mathbb R}^+  such that m_\delta \ge j  . A dyadic decomposition gives

E_3(A) = \sum_{\delta>0} m_\delta^3 = \sum_{j=1}^{\log n} \sum_{\substack{\delta>0  \\ 2^j \le m_\delta < 2^{j+1}}} m_\delta^3< \sum_{j=1}^{\log n} k_{2^j} 2^{3(j+1)}. \qquad \qquad \qquad (2)

For j\in {\mathbb N}  let \Delta_j  denote the set of \delta>0  with m_\delta\ge j  (so |\Delta_j| = k_j  ). For \delta >0  , let A_\delta  be the set of points that participate in at least one of the representations of \delta  . If there exist \delta_1,\delta_2, \delta_3  such that |A_{\delta_1} \cap A_{\delta_2} \cap A_{\delta_3}| \ge k/4  , then there exist a subset A'\subset A  with |A'|=k  and |A'-A'|< \binom{k}{2}-\frac{3k}{4}+13  (see the paper for a full explanation). Thus, for every \delta_1,\delta_2, \delta_3  we have that |A_{\delta_1} \cap A_{\delta_2} \cap A_{\delta_3}| < k/4  .

We have k_j  sets A_\delta  with |A_\delta| \ge j  . These are all subsets of the same set A  of size n  , and every three intersect in fewer than k/4  elements. We now have a set theoretic problem: How many large subsets can A  have with no three having a large intersection. We can use the following counting lemma (for example, see Lemma 2.3 of Jukna’s Extremal Combinatorics) to obtain an upper bound on k_j  .

Lemma 2. Let A  be a set of n  elements and let d\ge 2  be an integer. Let A_1,\ldots,A_k  be subsets of A  , each of size at least m  . If k \ge 2d n^d/m^d  then there exist 1\le j_1 < \ldots < j_d \le d  such that |A_{j_1}\cap \ldots \cap A_{j_d}| \ge \frac{m^d}{2n^{d-1}}  .

Lemma 2 implies the bound k_j = O(n^3/j^3)  for large values of j  . Combining this with (2)  and with a couple of standard arguments leads to E_3(A) = O(n^{10/3})  . Combining this with E_3(A) \ge \frac{n^6}{|A-A|^2}  implies |A-A|=\Omega(n^{4/3})  . \Box