Or Ordentlich, Oded Regev and Barak Weiss: New bounds for Covering Density!

Barak Weiss lectured about his breakthrough results with Or Ordentlich, and Oded Regev, at a Simons Institute workshop: Lattices: Geometry, Algorithms and Hardness.

It is a famous problem what is the densest (or, most efficient) packing of unit balls in Euclidean n-dimensional spaces and, of course, you can ask the same questions for other convex bodies. A sort of a dual problem, also famous, is the question of the most efficient covering the n-dimensional Euclidean space by balls or by translates of other convex bodies.

A very basic insight is that covering is much more efficient than packing. Can you explain the reason for that? The only thing that came up to my mind was that convex sets are roundish from the outside but not from the inside which makes it easier to cover with them.

But how efficiently can we cover the n-dimensional Euclidean space with translates of a convex body $K$?

C.A. Rogers with coauthors had some very fundamental results regarding covering (and packing) in the 50s and 60s. Or Ordentlich, Oded Regev and Barak Weiss have made a terrific improvement for one of the main questions in this area. They showed that for every convex set K, you can find a lattice of determinant 1, and r>0  such that rK+L = \mathbb R^n and

{\rm vol} (rK) \le cn^2.

The best earlier upper bound was n^{\log \log n}.

One surprising aspect of the proof is the use of finite field Kakeya-type questions. Since the breakthrough by Zeev Dvir, many people had hopes for applications from the finite fields results to the Euclidean setting (in particular, to the Euclidean Kakeya problem itself) and it is rare to see such applications. The proof here relies on results by  Dvir, Kopparty, Saraf, Sudan, and Lev. The Ordentlich-Regev-Weiss paper is not yet on the arXiv but the lecture gives a good picture about the results and the proofs.

The definition of the covering density of L with respect to a convex body K

The definition of the covering density of K

Old results for the Euclidean ball

Old results for general convex bodies

The first main result

 

The required finite field Kakeya theorem.

Posted in Combinatorics, Computer Science and Optimization, Geometry | Tagged , , | 2 Comments

To cheer you up in complicated times – A book proof by Rom Pinchasi and Alexandr Polyanskii for a 1978 Conjecture by Erdős and Purdy!

Things do not look that good, and these are difficult times. But here on the blog we have plenty of things to cheer you up and assure you. And today we point to two book proofs — two book proofs to the same theorem– and, as a matter of fact, two book proofs to the same theorem by the same person, Rom Pinchasi.  One of the proofs, the one chosen for presentation, is by Rom Pinchasi and  Alexandr Polyanskii.

Rom Pinchasi has an immense proving power, both for difficult proofs at all costs, for book proofs, and for a large variety of proofs in between. (See, for example,  this post.)

Before moving on, let me mention that there is a timely blog post by Terry Tao on Online teaching, and here is a related MO question about online conferences that I asked last December.

Proofs from the book

Famously, the mathematician Paul Erdős, often referred to “The Book” in which God keeps the most elegant proof of each mathematical theorem. During a lecture in 1985, Erdős said, “You don’t have to believe in God, but you should believe in The Book.” (And you do not have even to believe in the book to enjoy proofs from the book.)

The Theorem: a 1978 conjecture by Erdős and Purdy

Theorem:  Let P be a set of n points in general position in the plane. Suppose that R is a set of red points disjoint from P such that every line determined by P passes through a point in R. Then |R|≥ n for n > 6.

This theorem settles a problem by Erdős and Purdy from 1978. Erdős and Purdy also asked about the case where the set of points is not required to be in general position. For that problem the best known lower bound, also proved by Rom Pinchasi, is n/3.

Book Proof I: An algebraic solution of a problem of Erdős and Purdy, by Rom Pinchasi

Book Proof II: A one-page solution of a problem of Erdős and Purdy, by Rom Pinchasi and Alexandr Polyanskii

Murty’s magic configurations conjecture.

The first proof of the Erdős-Purdy 1978 Conjecture was achieved in 2008 by Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Günter Rote. They derived it from their solution to the 1971 conjecture on magic configurations by Murty. A planar set of points P is called magic if it possible to assign positive weights to the points so that the sum of weights in every line determined by the points is one. Murty conjectured that the only magic configurations are those in general position, and those which have a line missing at most one of the points, and a certain configuration of seven points.

The Pinchasi-Polyanskii Book-Proof:

Here, we very closely follow the Pinchasi-Polyanskii’s paper.

We say that a line is determined by a set of points in the plane if it contains at least two of the points. Since the points in P are in general position, each pair of points determines a different line.

Under the contrary assumption we must have |R| = n−1. Then it must be that every point in R is incident to precisely n/2 lines determined by P and every line determined by P is incident to precisely one point in R. We would like to reach a contradiction.

Preliminary step: apply a projective transformation to the plane such that the convex hull of P becomes a triangle.

Observation 1:  No point of R lies outside the convex hull of P.

Such a point r should be incident to two lines supporting the convex hull of P. Each of these supporting lines must contain precisely two points of P. Since the convex hull of P is a triangle this is impossible.

Regard the points in the plane as complex numbers.

(This is really cool. I am not aware of many examples in discrete geometry that thinking about planar points as complex numbers helps.)

Notation: for every point p in the plane we denote by p_x  the x-coordinate of p.

Crucial definition: For every point p ∈ P define

f(p) = \prod_{r \in R}(p-r) / \prod_{p' \in P\backslash \{p\}}(p-p').

Observation 2: f(p) is a real number!

The proof will surely make you smile: For every p’ ∈ P \{p} there is a unique r ∈ R such that p, p’, and r are collinear. So (p-r)/(p-p’) is real. And the big ratio between products split to many small fractions that are all real.  Walla!

Note that f(p) is thus also invariant under rotations of the plane.

Now, if the vertical line through p does not contain any other point in P ∪ R, then, for the unique r ∈ R such that p, p’, and r are collinear, we have that:

(1)~~~(p-r)/(p-p')~=~(p_x-r_x)/(p_x-p'_x).

This leads to:

Observation 3:  if the vertical line through p does not contain any other point in P ∪ R, then

(2)~~~ f(p) = \prod_{r \in R}(p_x-r_x) / \prod_{p' \in P\backslash \{p\}}(p_x-p'_x).

Crucial observation 4:  Let p and q be any two points in P and let r be the unique point in R collinear with p and q. Then

f(p)/f(q)=-(p-r)/(q-r).

To see this rotate the plane so that the x-coordinates of p,q, and r are equal (or nearly equal) and apply Equations (2) and (1). (You will get the same, or nearly the same, contributions for r’ ≠ r  and you are left with the contribution for r. ) This also leads to:

Observation 5: f(p)/f(q) >0  if and only if the unique point r ∈ R that is collinear with p and q lies in the straight line segment delimited by p and q.

A complete graph with green and red edges.

Consider the complete graph G whose vertices are the points in P. For every two points p, q ∈ P we color the edge connecting  p and q red if the unique point in R collinear with p and q lies outside the straight line segment connecting p and q. Otherwise we color the edge green. In other words, the edge is red if f(p)/f(q) < 0, and green if f(p)/f(q) > 0.

The vertices of G can naturally be partitioned into two sets: U = {p ∈ P | f(p) > 0} and W = {p ∈ P | f(p) < 0}.

Without loss of generality assume that the three vertices of the convex hull of P belong to U. (Since no point of R is outside this convex hull all edges of the triangle forming the convex hull are green.)

Observation 6: |U| = n/2 + 1.

To see this let a,bU be two vertices of the convex hull of P. Let cR be the point in R collinear with a and b. The point c must be between a and b on the boundary of the convex hull of P. Therefore, all the other n/2 −1 pairs of points of P that are collinear with c must form red edges. Consequently, precisely one point of every such pair belongs to U. Together with a and b, we obtain |U| = n/2+1.

End of proof:

Continue reading

Posted in Combinatorics, Geometry, What is Mathematics | Tagged , | 8 Comments

A new PolyTCS blog!

A new PolyTCS blog

The PolyTCS Project is a new blog to run collaborative Theoretical Computer Science projects. The initiative is by two graduate students Rupei Xu and Chloe Yang. The logo was designed by Grigory Yaroslavtsev.

At this stage the blog raised possible projects to pursue.  A few days ago Rupei Xu discussed a second possible exciting project:   Project 2: Is Semi-Definite Programming (SDP) Polynomial-Time Solvable? The first project-proposal (Nov 1, 2019 by Jiapeng Zhang) was Project 1: The Entropy-Influence Conjecture.

(Here is a 2014  post on GLL on the problem of Project 2, and here is my 2007 post on WN on the problem of Project 1.)

Good luck!!!

 

Posted in Combinatorics, Computer Science and Optimization, Mathematics over the Internet | Tagged , , | Leave a comment

Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand

 

The main conjecture from Talagrand’s paper on boundaries and influences was settled by Ronen Eldan and Renan Gross. Their paper introduces a new powerful method to the field of analysis of Boolean functions (ABF).

This post is devoted to a new breakthrough paper by Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.

The paper introduces remarkable new techniques based on stochastic calculus, (that bypass the use of hypercontractivity), that allow to settles several open problems on analysis of Boolean functions. (And on the way, to give a very different proof for KKL.)

Renan Gross recently wrote an excellent high-level explanation of the paper in his  blog: New paper on arXiv: Concentration on the Boolean hypercube via pathwise stochastic analysis. It is accompanied by a brief introduction to Boolean analysis, featuring the required Boolean material:

 

Before we move on, a trivia question:

Trivia question: Who invented the term hypercontractivity?

(For a hint, see at the end of the post.)

Back to the paper by Ronen Eldan and Renan Gross. Perhaps the best way to explain what was achieved in this paper is to put one after the other the abstracts of the first version followed by the abstract of the second paper.

 

Ronen and Renan’s paper. Version 1, 26 Sept 2019.

The title for version 1 was: Stability of Talagrand’s influence inequality

And here is the abstract: 

We strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function

(1)~~~~~\mathrm{var}\left(f\right)\leq C\sum_{i=1}^{n}\frac{\mathrm{Inf}_{i}\left(f\right)}{1+\log\left(1/\mathrm{Inf}_{i}\left(f\right)\right)}

where  \mathrm{Inf}_{i}\left(f\right) denote the influence of the i-th coordinate. We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial (KKL) inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary. Our proofs rely on new techniques, based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.

Let me say a few words about it. KKL theorem asserts that the maximal influence of a balanced Boolean function is at least \Omega (\log n/n) var (f). The famous tribe example of Ben-Or and Linial shows that this is tight.  The KKL paper gave some statements about other norms of the influence vector and Talagrand’s inequality stated above (from the paper “On Russo’s 0-1 law”) gives a sharp description of the influence vectors. Ronen and Renan found a new method that gave new proofs for KKL’s theorem and the stronger Talagrand’s inequality. This new methods led to new stability result.

Now, lets move to version 2.

Ronen and Renan’s paper: Version 2: 12 Nov 2019,

Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.

Abstract: We develop a new technique for proving concentration inequalities which relate between the variance and influences of Boolean functions. Using this technique, we

1. Settle a conjecture of Talagrand [Tal97] proving that

(2)~~~~~\int_{\left\{ -1,1\right\} ^{n}}\sqrt{h_{f}\left(x\right)}d\mu\geq C\cdot\mathrm{var}\left(f\right)\cdot\left(\log\left(\frac{1}{\sum\mathrm{Inf}_{i}^{2}\left(f\right)}\right)\right)^{1/2},

where h_f(x) is the number of edges at x  along which f changes its value, and Inf_i(f) is the influence of the i-th coordinate.

2. Strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function f

\mathrm{var}\left(f\right)\leq C\sum_{i=1}^{n}\frac{\mathrm{Inf}_{i}\left(f\right)}{1+\log\left(1/\mathrm{Inf}_{i}\left(f\right)\right)}

We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary.

3. Improve a quantitative relation between influences and noise stability given by Keller and Kindler.

Our proofs rely on techniques based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.

Let me explain in a few words the main inequality that verified a conjecture by Talagrand. For other advances look at the paper itself.

The famous Margulis-Talagrand inequality asserts that

(3)~~~~~\int_{\left\{ -1,1\right\} ^{n}}\sqrt{h_{f}\left(x\right)}d\mu\geq C\cdot\mathrm{var}(f).

Let me say a little more. Talagrand’s proved in  his paper on Influence and boundary asserts that the right hand is a constant only if II(f) – the sum of squares of the influences is a constant. He conjectured that we can actually add the square root of \log II(f) to the RHS.

A few remarks:

  1.  For more background see my old post “Nati’s influence“.
  2. Let me mention that Talagrand’s influence inequality (Equation (1) above) is sharp up to a multiplicative constant. This is shown in a 2015 paper: On the Converse of Talagrand’s Influence Inequality by Saleet Klein, Amit Levi, Muli Safra, Clara Shikhelman, and Yinon Spinka.
  3.  Finding the best constant in KKL’s theorem is a well known challenge. So is the question of understanding balanced Boolean functions on n variables where the maximum influence is C \log n/n. Ehud Friedgit in his paper: Influences in Product Spaces, KKL and BKKKL Revisited, have made important conjectures for such Boolean functions.
  4.  I expect that the new method will have many applications. Ronen Eldan in a paper Second-order bounds on correlations between increasing families, found applicaions to correlation inequalities which I will discuss at some other time.
  5.  See the last part of this post for a description of Talagrand’s various relevant papers.
  6. Renan Gross is building the BooleanZoo in a similar spirit to the famous complexityZoo.
  7. I was in the process of writing a post about progress on ABS, mentioning twelve or so papers, apologizing for not mentioning others, promising to write in details about some of the papers, and making further apologetic remarks. But as this large post does not advance let me start with some of the promises.

talabb

Hint to the trivia question:

Continue reading

Posted in Analysis, Combinatorics, Probability | Tagged , , | 5 Comments

Hoi Nguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective

Following a lecture by Hoi Nguyen at Oberwolfach, I would like to tell you a little about the paper: Random integral matrices: universality of surjectivity and the cokernel by Hoi Nguyen and Melanie Wood.

Two background questions:

Hoi started with two background questions –

Background Question 1: Consider an n \times n 0-1 matrix where the entries are taken at random. What is the probability that the matrix is singular (over the rationals)?

Hoi mentioned the recent result of Konstantin Tikhomirov, and moved to talk about matrices over the integers.

Background Question 2: Now, think about the lattice spanned by the rows of the matrix. How likely it is that this is the full \mathbb Z^n? (In other words that the determinant is +1 or -1.)

Probably, I thought, the answer is less than exponentially small.

The main question

Hoi moved quickly to the main question

Main question: Now think about the rows of a random 0-1 (n+1) \times n matrix. How likely it is that this is the full \mathbb Z^n?

Hmm, I was not sure how quickly the answer should tend to zero. But I learnt quickly that the answer does not tend to zero at all!

A remarkable heuristic formula: the probability for a random integral matrix from (n+1)-dimensions to n-dimenssions to be surjective is

one over  (ζ(2)ζ(3)ζ(4)ζ(5)…) 

What would justify this formula? Hoi described the following heuristic argument.

  1. To be surjective you need to be surjective modulo p for every prime number p.
  2.  Take some p. The probability to be surjective modulo p when the entries are uniformly random (independently) numbers modulo p is \prod_{j=2}^{n+1}(1-p^{-j}).
  3. This probability continues to work if you consider 0-1 entries.
  4. You can assume that all these probabilities for different primes are statistically independent.
  5. When you multiply all these probabilities you get

\zeta(2)^{-1}\zeta(3)^{-1}\zeta(5)^{-1}\zeta(7)^{-1}\cdots

When Hoi reached this formula in his Oberfolfach lecture my immediate thought was this: This is a remarkable formula; maybe it is even true although it looks very hard to justify the two crucial steps  in the heuristics. Why you can assume that 0-1 matrices behave like random matrices with uniform entries and why we have statistical independence that allows us to multiply probabilities just like in high school probability class? And maybe it is not true.

(This heuristics is known as the Cohen Lenstra heuristics and it was made for understanding the structure of class groups of quadratic fields.)

And then came the next slide of the presentation.

 

Hoi Nguyen and Melanie Wood actually proved this formula!

This is  a special case of a considerably more general formula. Look at the paper for more details and for the proofs.

It looks to me that the proof is tour de force and it uses various difficult and delicious techniques and earlier results. Various new and old Littlewood-Offord type results which are independently interesting are used.

And here is a related paper by Hoi and Melanie: Cokernels of adjacency matrices of random r-regular graphs.

 

Little more

As mentioned in the Nguyen-Wood paper, Shaked Koplewitz   roposed and proved some cases the Cohen-Lenstra heuristic for integral n by n+k matrices. (See Skaed’s comment below.)

As for background problem 2, the paper mentioned that the fact that the probability tends to 0 follows from Corollary 3.4 from a paper by Melanie Wood: Random integral matrices and the Cohen Lenstra Heuristics.  (Maybe there are different avenues for showing that there is a vanishing probability for every specific value of the determinant as well.) I don’t know if it is known that the probability that the determinant is 1 is exponentially small. (You can guess it is like square root of n! or something like that.) Also I don’t know if the ratio between the probabilities that the determinant is 3 and that it is 7 respects the Cohen Lenstra heuristics. Do we expect it at all? You can regard the determinant as a strange random walk so what is the reason that stopping at 3 will be different than stopping at 7?  It is also not known and this is raised as a question in the paper if the probability that the determinant is a perfect square respects the Cohen-Lenstra heuristics (and this seems reasonable).

There are similar nice questions for simplicial complexes. See the paper Cohen–Lenstra heuristics for torsion in homology of random complexes, by Matthew Kahle, Frank Lutz, Andrew Newman, and Kyle Parsons.

So if you consider the torsion of the 7 dimensional homology of a random 14 dimensional manifolds. Then (unless there are theorems to the contrary) it is natural to guess that the torsion will obey a Cohen-Lenstra heuristic of some kind.  This also applies to rationally acyclic complexes (hypertrees) and various other gadgets.

 

Posted in Algebra, Combinatorics, Number theory, Probability | Tagged , | 6 Comments

Petra! Jordan!

Last week we had a lovely small workshop in Eilat organized by Nathan Rubin, and as possible since the peace agreement of 1994 between Israel and Jordan, we visited Jordan for one day and saw the spectacular ancient city of Petra. Here are some pictures from Petra and Eilat.

With Andreas Holmsen, Janos Pach, and Gabor Tardos.

  

And a couple pictures from Eilat

 

Posted in Uncategorized | Tagged , , | Leave a comment

The largest clique in the Paley Graph: unexpected significant progress and surprising connections.

The result on Paley Graphs by Hanson and Petridis

On May 2019, Brandon Hanson and Giorgis Petridis posed a paper on the arXive: Refined Estimates Concerning Sumsets Contained in the Roots of Unity. The abstract was almost as short as the title (the paper is short as well!):

We prove that the clique number of the Paley graph is at most \sqrt {p/2}+1, and that any supposed additive decompositions of the set of quadratic residues can only come from co-Sidon sets.

Let me elaborate on the first half of the abstract.

Let q be a prime power such that q=1 (\mod 4). This choice implies that in F_q the difference of two numbers, a-b, is a square iff -(a-b) is a square, so the Paley graph we are going to define is a simple graph.

In the Payley graph the vertices are the elements of F_q and two are adjacent iff their difference is a square.

When the field is F_p, where p is prime, then the Paley graph is conjectured to be an excellent construction for a Ramsey graphs, the largest complete subgraph (which has the same size as its largest empty subgraph since it is self-complementary) is conjectured to be \log(p)\log \log (p). This is actually a lower bound for infinitely many primes, proved by Montgomery under the assumption that the generalized Riemann hypothesis holds.

The upper bound (which is easy to prove) is \sqrt p. This upper bound is sharp for the field F_{p^2}. (This is a very nice construction of Aart Blokhuis.)

There was practically no improvement on the \sqrt p upper bound until 2013, when Bachoc, Ruzsa and Matolcsi, proved that the \sqrt p-1 bound holds for infinitely many primes.

Hanson and Petridis thus improved the upper bound significantly! They gave the upper bound \sqrt{p/2}+1 on the clique size of the Paley graph. Their  proof uses Stepanov’s method.

The result of Di Benedetto, Solymosi, and White on directions in Cartesian products

A couple weeks ago, Daniel Di Benedetto, József Solymosi, and Ethan White posted a paper on the arxive: On the directions determined by a Cartesian product in an affine Galois plane. Also here the abstract is also quite short (and so is the entire paper!).

We prove that the number of directions contained in a set of the form A \times B \subset AG(2,p), where p is prime, is at least |A||B| -\min\{|A|,|B|\}+2. Here A and B are subsets of GF(p) each with at least two elements and |A||B|<p. This bound is tight for an infinite class of examples. Our main tool is the use of the Rédei polynomial with Szőnyi’s extension.

A surprising connection

Now, if you have a set A where the difference between any two elements is a square then in A \times A all directions, (a-b)/(c-d), are also squares. To Daniel, József, and Ethan’s  great surprise applying their bound on the clique number of the Paley graph gave the very same bound as Hanson and Petridis!

I am thankful to Józsi Solymosi for very helpful clarifications.

Payley graph with 13 vertices (source: wikipedea)

A quick Sum-Product update, and associations.

Now that I mention Józsi’s work let me also use this opportunity to give a quick update about Erdős-Szemeredi’s sum product conjecture. In an old post from 2009, I presented Elekes’ pioneering geometric proof for his sum-product world record and gave a link to a paper and a blog post written by Izabella Laba about József Solymosi’s new (then) world record. I just saw an article by Kevin Hartnett about the problem in Quanta Magazine describing several subsequent records. The current world record is in a 2019 paper by George Shakan.   (Sergei Konyagin and Ilya Shkredov broke József’s record in 2015, and the new record improved a 2016 world record by Misha Rudnev, Ilya Shkredov and Sophie Stevens; I also updated my related MO answer.) Of course, the sum-product phenomena is a huge area with amazing applications (See, here, here, here, and here; I recall that Jean Bourgain referred to it as a gold mine or something like that). Now, talking about sum-product theorems, and about Bourgain, and about Quanta Magazine, I should mention a lovely Quanta podcast featuring Alex Kontorovich interviewed by Steven Strogatz  .

Posted in Combinatorics, Number theory | Tagged , , , , , | 2 Comments

Thinking about the people of Wuhan and China

My thoughts are with the people of China who are at the forefront of the struggle with the coronavirus outbreak.

Posted in Uncategorized | Tagged , , | 1 Comment

Ringel Conjecture, Solved! Congratulations to Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov

Ringel’s conjecture solved (for sufficiently large n)

A couple weeks ago and a few days after I heard an excellent lecture about it by Alexey Pokrovskiy in Oberwolfach, the paper A proof of Ringel’s Conjecture by Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov was arXived. Congratulations to Richard, Alexey, and Benny!

Here is the abstract:

A typical decomposition question asks whether the edges of some graph G can be partitioned into disjoint copies of another graph H. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of complete graphs into edge-disjoint copies of a tree. It says that any tree with n edges packs 2n+1 times into the complete graph K_{2n+1}. In this paper, we prove this conjecture for large n.

Previous posts: Test your intuition 43 – What will be the distribution of anabraists and algasisits; MIP*=RE. For Ringel’s circle conjecture, see this post.

Absorption and distributive absorption

First the authors construct approximate decomposition (they divide the problem into two cases) and then they apply a powerful method called absorption. Here is what they write:

To prove our finishing lemmas, we use an absorption strategy. Absorption has its origins in work by Erdős, Gyárfás and Pyber [5] and Krivelevich [14], but was codified by Rödl, Ruciński and Szemerédi [20] as a versatile technique for extending approximate results into exact ones. For both Case A and Case B we use a new implementation of distributive absorption, a method introduced by the first author in [16].

Absorption is one of the most powerful current methods in extremal combinatorics. It is important in the construction of designs (See here, here, here, and here, and my own survey), and in the the solution of several other important conjectures.

Here are links to the pioneering papers mentioned above.

P. Erdős, A. Gyárfás and L. Pyber [5] Vertex coverings by monochromatic cycles and trees. Journal of Combinatorial Theory, Series B, 90–95, 1991.

M. Krivelevich [14] Triangle factors in random graphs. Combinatorics, Probability and Computing, 6: 337–347, 1997.

V. Rödl, A. Ruciński and E. Szemerédi [20] A dirac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput., 15:229–251, 2006.

And Montgomery’s paper on distributive absorption:

R. Montgomery [16] Spanning trees in random graphs, Advances in Mathematics, 2019

A related paper with an amusing name and an amusing abstract is:  E. Szemerédi “Is laziness paying off? (`Absorbing’ method).”  The abstract of the paper reads “We are going to mention some embedding problems. The main ideas of most of the solution of these problems are that do not work too much. Finish the job almost, then use some kind of absorbing configuration (that is what we call laziness).”

Montgomery, Pokrovskiy, and Sudakov’s paper concludes with two related famous conjectures:

The graceful tree conjecture

Motivated by Ringel’s conjecture, in 1967 Alexander Rosa conjectured that every tree T with n edges admits a graceful labeling, namely a labeling of the vertices by the numbers 0,1,…,n such that if we label an edge by the absolute value of the difference of the labels for its two vertices, then all the edge labels are different!

This famous conjecture (stronger than Ringel’s conjecture) is known as the Graceful Tree conjecture and also as the Ringel-Rosa-Kötzig conjecture. It is still open.

Packing trees of different sizes: Gyárfás conjecture

Gyárfás conjecture (1976): Let T_1, \dots ,T_n be trees with T_i having i vertices for each i=1,2,\dots,n. Then the edges of K_n can be decomposed into n trees which are isomorphic to T_1, \dots ,T_n respectively.

 

Posted in Combinatorics, Open problems, Updates | Tagged , , | 3 Comments

Test your intuition 43: Distribution According to Areas in Top Departments.

 

In the community of mamathetitians in a certain country there are mamathetitians in two areas: Anabra (fraction p of the mamathetitians) and Algasis (fraction 1-p of  mamathetitians.) There are ten universities with 50 faculty members in each mamathetics department and there is a clear ranking of these universities from best to worse. (So a better university pays higher salary and gives better working conditions.)  Every year 40 fresh Ph D’s are in the job market and each university  hires two of the fresh Ph. D.’s as new faculty members replacing retired faculty members.

The objective value v(x) of every mamathetitian x is a random variable uniformly distributed in the interval [0,1]The subjective value of x in the eyes of another mamathetitian y is v(x)+t if they belong to the same area and v(x)-t if they belong to different areas, where t is a small real number.

The top ranked university hires the best two fresh Ph. D.’s  according to average value in the eyes of the faculty, the second university hires the second best two students etc.

Let’s assume that to start is p=0.25, so 25% of all faculty are anabraists, and 75% are algasisits and this is the ratio in every university. Let us also assume that among the students for ever 25% are anabraists, and 75% are algasisits.

Test your intuition (and/or, programming skills) 43: What will be the distribution of anabraists and algasisits in the departments as time advances (depending on t), what will be the stationary distribution across departments?

We can also ask about variations to the model:

Further test you intuition, imagination and programming skill: How does the answer change if you change the model in various ways. Change the value of p? Make the initial distribution random across departments?  Add noise to the subjective value? Make the bias in subjective evaluation asymmetric? make different assumptions on the fresh Ph. D.s? etc. etc.

References to similar models considered in the literature are most welcome.

Disclaimer: I do not know the answers.

Outcomes by Joshua Paik

Here are very interesting outcomes by Joshua Paik. We see a sort of Zebra-strips patterns between Algasis dominated departments and Anabra dominated departments.

Posted in Combinatorics, Open problems, Probability, Test your intuition | Tagged | 9 Comments