Zarankiewicz's problem

125 Views Asked by At

I was reading about Zarankiewicz's problem from the book "Extremal combinatorics" by Stasys Jukna. The problem sounds very interesting and I was about to understand some basics about it. Here I am attaching an excerpt from the book: enter image description here

Here is my question: So we have two objects:

  1. the maximal number of $1$'s in a $0-1$ matrix of size $n\times n$ such that any $a\times a$ submatrix has at least one $0$ among its entries. Here we assume that $n\geq a\geq 2$. For concreteness let's denote it by $m_a(n)$.

  2. $k_a(n)=\min \mathfrak{C}$, where $\mathfrak{C}$ is the set of all $k \in \mathbb N$ such that any bipartite graph with parts of size $n$ and more than $k$ edges contains at least one $a\times a$ clique.

Question 1: 1) I guess that $\min \mathfrak{C}$ exists because $n^2-1\in \mathfrak{C}$. It also shows very trivial estimate $k_a(n)\leq n^2-1$. Right?

Question 2: I was able to show that $m_a(n)\leq k_a(n)$. Am I right that we cannot claim the converse inequality, i.e. $m_a(n)\geq k_a(n)$ right?