The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size.^[1] It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951.^[2]

Problem statement

A bipartite graph ${\displaystyle G=(U\cup V,E)}$ consists of two disjoint sets of vertices ${\displaystyle U}$ and ${\displaystyle V}$, and a set of edges each of which connects a vertex in ${\displaystyle U}$ to a vertex in ${\displaystyle V}$. No two edges can both connect the same pair of vertices. A complete bipartite graph is a bipartite graph in which every pair of a vertex from ${\displaystyle U}$ and a vertex from ${\displaystyle V}$ is connected to each other. A complete bipartite graph in which ${\displaystyle U}$ has ${\displaystyle s}$ vertices and ${\displaystyle V}$ has ${\displaystyle t}$ vertices is denoted ${\displaystyle K_{s,t}}$. If ${\displaystyle G=(U\cup V,E)}$ is a bipartite graph, and there exists a set of ${\displaystyle s}$ vertices of ${\displaystyle U}$ and ${\displaystyle t}$ vertices of ${\displaystyle V}$ that are all connected to each other, then these vertices induce a subgraph of the form ${\displaystyle K_{s,t}}$. (In this formulation, the ordering of ${\displaystyle s}$ and ${\displaystyle t}$ is significant: the set of ${\displaystyle s}$ vertices must be from ${\displaystyle U}$ and the set of ${\displaystyle t}$ vertices must be from ${\displaystyle V}$, not vice versa.)

The Zarankiewicz function ${\displaystyle z(m,n;s,t)}$ denotes the maximum possible number of edges in a bipartite graph ${\displaystyle G=(U\cup V,E)}$ for which ${\displaystyle |U|=m}$ and ${\displaystyle |V|=n}$, but which does not contain a subgraph of the form ${\displaystyle K_{s,t}}$. As a shorthand for an important special case, ${\displaystyle z(n;t)}$ is the same as ${\displaystyle z(n,n;t,t)}$. The Zarankiewicz problem asks for a formula for the Zarankiewicz function, or (failing that) for tight asymptotic bounds on the growth rate of ${\displaystyle z(n;t)}$ assuming that ${\displaystyle t}$ is a fixed constant, in the limit as ${\displaystyle n}$ goes to infinity.

For ${\displaystyle s=t=2}$ this problem is the same as determining cages with girth six. The Zarankiewicz problem, cages and finite geometry are strongly interrelated.^[3]

The same problem can also be formulated in terms of digital geometry. The possible edges of a bipartite graph ${\displaystyle G=(U\cup V,E)}$ can be visualized as the points of a ${\displaystyle |U|\times |V|}$ rectangle in the integer lattice, and a complete subgraph is a set of rows and columns in this rectangle in which all points are present. Thus, ${\displaystyle z(m,n;s,t)}$ denotes the maximum number of points that can be placed within an ${\displaystyle m\times n}$ grid in such a way that no subset of rows and columns forms a complete ${\displaystyle s\times t}$ grid.^[4] An alternative and equivalent definition is that ${\displaystyle z(m,n;s,t)}$ is the smallest integer ${\displaystyle k}$ such that every (0,1)-matrix of size ${\displaystyle m\times n}$ with ${\displaystyle k+1}$ ones must have a set of ${\displaystyle s}$ rows and ${\displaystyle t}$ columns such that the corresponding ${\displaystyle s\times t}$ submatrix is made up only of 1s.

Examples

The number ${\displaystyle z(n;2)}$ asks for the maximum number of edges in a bipartite graph with ${\displaystyle n}$ vertices on each side that has no 4-cycle (its girth is six or more). Thus, ${\displaystyle z(2;2)=3}$ (achieved by a three-edge path), and ${\displaystyle z(3;2)=6}$ (a hexagon).

In his original formulation of the problem, Zarankiewicz asked for the values of ${\displaystyle z(n;3)}$ for ${\displaystyle n=4,5,6}$. The answers were supplied soon afterwards by Wacław Sierpiński: ${\displaystyle z(4;3)=13}$, ${\displaystyle z(5;3)=20}$, and ${\displaystyle z(6;3)=}$Zdroj:https://en.wikipedia.org?pojem=Zarankiewicz_problem
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.