KAIST Discrete Math Seminar

We study algebraic analogues of the graph Removal Lemma. Vaguely speaking, the graph Removal Lemma says that if a given graph does not contain too many subgraphs of a given kind, then all the subgraphs of this kind can be destroyed by removing few edges. In 2005, Green conjectured the following analogue of it for systems of equations over integers:

For every k x m integral matrix A with rank k and every ε>0, there exists δ>0 such that the following holds for every N and every subset S of {1,…N}: if the number of solutions of A x = 0 with x ∈ S^m is at most δ N^{m-k}, then it is possible to destroy all solutions x ∈ S^m of A x = 0 by removing at most ε N elements from the set S.

We prove this conjecture by establishing its variant for not necessarily homogenous systems of equations over finite fields. The core of our proof is a reduction of the statement to the colored version of hypergraph Removal Lemma for (k+1)-uniform hypergraphs. Independently of us, Shapira obtained the same result using a reduction to the colored version of hypergraph Removal Lemma for O(m²)-uniform hypergraphs. The talk will be self-contained and no previous knowledge of the area related to the graph Removal Lemma will be assumed.

Joint work with Oriol Serra and Lluis Vena.

Inspired by the famous virtual Haken conjecture in 3–manifold theory, Gromov asked whether every one-ended word-hyperbolic group contains a surface group. One simple, but still captivating case, is when the word-hyperbolic group is given as the double of a free group with a cyclic edge group. In the first part of the talk, I will describe the polygonality of a word in a free group, and a relation between polygonality and Gromov’s question. Polygonality is a combinatorial property, which is very much like solving a “topological jigsaw puzzle”. In the second part, I will describe a reduction to a purely (finite) graph theoretic conjecture using the Whitehead graph. Part I is a joint word with Henry Wilton (Caltech).

We consider the problem Max-r-SAT, an extensively studied variant of the classic satisfiability problem. Given an instance of CNF (Conjunctive normal form) in which each clause consists of exactly r literals, we seek to find a satisfying truth assignment that maximizes the number of satisfied clauses. Even when r=2, the problem is intractable unless P=NP. Hence the next quest is how close we can get to optimality with moderate usage of computation time/space.

We present an algorithm that decides, for every fixed r≥2 in time O(m) + 2^O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2^r-1)m+k)/2^r clauses. Our algorithm is based on a polynomial-time preprocessing procedure that reduces a problem instance to an equivalent algebraically represented problem with O(k²) variables. Moreover, by combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that an instance of Max-2-Sat either is a YES-instance or can be transformed into an equivalent instance of size at most 3k.

This is a joint work with Noga Alon, Gregory Gutin, Stefan Szeider, and Anders Yeo.

I am going to give a survey on several basic problems of combinatorial nature concerning random Bernoulli matrices, including:

(1) The singularity problem: What is the probability that a random Bernoulli matrix is singular?

(2) The determinant problem: What is the typical value of the determinant?

(3) The permanent problem: What is the typical value of the permanent?

(4) The eigenvector problem: How does a typical eigenvector look like?

If time allows, I will discuss connections to other areas of mathematics, most importantly additive combinatorics.

We present a coefficient formula which provides some information about the polynomial map when only incomplete information about a polynomial is given. It is an integrative generalization and sharpening of several known results and has many applications, among these are:

1. The fact that polynomials in just one variable have at most deg(P) roots.
2. Alon and Tarsi’s Combinatorial Nullstellensatz.
3. Chevalley and Warning’s Theorem about the number of simultaneous zeros of systems of polynomials over finite fields.
4. Ryser’s Permanent Formula.
5. Alon’s Permanent Lemma.
6. Alon and Tarsi’s Theorem about orientations and colorings of graphs.
7. Scheim’s formula for the number of edge n-colorings of planar n-regular graphs.
8. Alon, Friedland and Kalai’s Theorem about regular subgraphs.
9. Alon and Füredi’s Theorem about cube covers.
10. Cauchy and Davenport’s Theorem from additive number theory.
11. Erdős, Ginzburg and Ziv’s Theorem from additive number theory.