Report

Teaser, summary, work performed and final results

Periodic Reporting for period 3 - EXTPRO (Quasi-Randomness in Extremal Combinatorics)

Teaser

In object is quasi-random if it behaves (in certain well defines ways) like we would expect a typical object to behave. The goal of this project is to better understand the role and the applicability of various notions of quasi-randomness in discrete mathematics, that is, in...

Summary

In object is quasi-random if it behaves (in certain well defines ways) like we would expect a typical object to behave. The goal of this project is to better understand the role and the applicability of various notions of quasi-randomness in discrete mathematics, that is, in the study of discrete objects such as networks, strings of characters. The surprising fact, is that we can study arbitrary object, that is, even those that do NOT behave like typical one, using tools developed to handle objects that do behave this way. For example, we might try to show that every string can be broken into few strings, each of which is quasi-random. This can allow us to prove theorems or design algorithms by making the assumption that the input has some nice properties (even though it doesn’t), thus making these tasks much easier.
Within the above framework, I mainly try to prove theorems on graph and hypergraphs specifically regarding the connections between local and global properties of such objects. I also try to use these insights in order to design very fast algorithms for solving various problem on such objects.

Work performed

The main results we have obtained are the following:
1. We obtained a tight bound for Green’s arithmetic regularity lemma.
2. We proved a tight bound for the hypergraph regularity lemma.
3. We laid out a new graph theoretic approach for solving a famous conjecture regarding the density of matrices avoiding certain patters.
4. We obtained a new proof of Fox’s famous bound for the graph removal lemma.
5. We obtained a new general sufficient for polynomially bounded removal lemmas. In particular, we proved that every semi-algebraic graph property has an efficient removal lemma.

Final results

1. Obtain polynomial bounds for the induced C_4 removal lemma
2. Find a characterization of the linear equations for which one can prove a polynomial bounds for their removal lemma.
3. Prove supersaturation results over product posets.

Website & more info

More info: http://www.math.tau.ac.il/.