In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a branch of mathematics, a -biclique-free
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
is a graph that has no -vertex
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
as a
subgraph. A family of graphs is biclique-free if there exists a number such that the graphs in the family are all -biclique-free. The biclique-free graph families form one of the most general types of
sparse graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction ...
family. They arise in incidence problems in
discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic ge ...
, and have also been used in
parameterized complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
.
Properties
Sparsity
According to the
Kővári–Sós–Turán theorem, every -vertex -biclique-free graph has edges, significantly fewer than a
dense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinctio ...
would have. Conversely, if a graph family is defined by
forbidden subgraphs or closed under the operation of taking subgraphs, and does not include dense graphs of arbitrarily large size, it must be -biclique-free for some , for otherwise it would include large dense complete bipartite graphs.
As a
lower bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an eleme ...
, conjectured that every maximal -biclique-free bipartite graph (one to which no more edges can be added without creating a -biclique) has at least edges, where and are the numbers of vertices on each side of its bipartition.
Relation to other types of sparse graph family
A graph with degeneracy is necessarily -biclique-free. Additionally, any
nowhere dense
In mathematics, a subset of a topological space is called nowhere dense or rare if its closure has empty interior. In a very loose sense, it is a set whose elements are not tightly clustered (as defined by the topology on the space) anywhere. ...
family of graphs is biclique-free. More generally, if there exists an -vertex graph that is not a 1-shallow minor of any graph in the family, then the family must be -biclique-free, because all -vertex graphs are 1-shallow minors of .
In this way, the biclique-free graph families unify two of the most general classes of sparse graphs.
[.]
Applications
Discrete geometry
In
discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic ge ...
, many types of
incidence graph are necessarily biclique-free. As a simple example, the graph of incidences between a finite set of points and lines in the
Euclidean plane necessarily has no subgraph.
Parameterized complexity
Biclique-free graphs have been used in
parameterized complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
to develop algorithms that are efficient for sparse graphs with suitably small input parameter values. In particular, finding a
dominating set
In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for .
The dominating set ...
of size , on -biclique-free graphs, is fixed-parameter tractable when parameterized by , even though there is strong evidence that this is not possible using alone as a parameter. Similar results are true for many variations of the dominating set problem.
It is also possible to test whether one dominating set of size at most can be converted to another one by a chain of vertex insertions and deletions, preserving the dominating property, with the same parameterization.
[.]
References
{{reflist
Extremal graph theory
Graph families