Property B

Last updated

In mathematics, Property B is a certain set theoretic property. Formally, given a finite set X, a collection C of subsets of X has Property B if we can partition X into two disjoint subsets Y and Z such that every set in C meets both Y and Z.

Contents

The property gets its name from mathematician Felix Bernstein, who first introduced the property in 1908. [1]

Property B is equivalent to 2-coloring the hypergraph described by the collection C. A hypergraph with property B is also called 2-colorable. [2] :468 Sometimes it is also called bipartite, by analogy to the bipartite graphs. Property B is often studied for uniform hypergraphs (set systems in which all subsets of the system have the same cardinality) but it has also been considered in the non-uniform case. [3]

The problem of checking whether a collection C has Property B is called the set splitting problem.

Smallest set-families without property B

The smallest number of sets in a collection of sets of size n such that C does not have Property B is denoted by m(n).

Known values of m(n)

It is known that m(1) = 1, m(2) = 3, and m(3) = 7 (as can by seen by the following examples); the value of m(4) = 23 (Östergård), although finding this result was the result of an exhaustive search. An upper bound of 23 (Seymour, Toft) and a lower bound of 21 (Manning) have been proven. At the time of this writing (March 2017), there is no OEIS entry for the sequence m(n) yet, due to the lack of terms known.

m(1)
For n = 1, set X = {1}, and C = {{1}}. Then C does not have Property B.
m(2)
For n = 2, set X = {1, 2, 3} and C = {{1, 2}, {1, 3}, {2, 3}} (a triangle). Then C does not have Property B, so m(2) <= 3. However, C' = {{1, 2}, {1, 3}} does (set Y = {1} and Z = {2, 3}), so m(2) >= 3.
m(3)
For n = 3, set X = {1, 2, 3, 4, 5, 6, 7}, and C = {{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3}} (the Steiner triple system S7); C does not have Property B (so m(3) <= 7), but if any element of C is omitted, then that element can be taken as Y, and the set of remaining elements C' will have Property B (so for this particular case, m(3) >= 7). One may check all other collections of 6 3-sets to see that all have Property B.
m(4)
Östergård (2014) through an exhaustive search found m(4) = 23. Seymour (1974) constructed a hypergraph on 11 vertices with 23 edges without Property B, which shows that m(4) <= 23. Manning (1995) narrowed the floor such that m(4) >= 21.

Asymptotics of m(n)

Erdős (1963) proved that for any collection of fewer than sets of size n, there exists a 2-coloring in which all set are bichromatic. The proof is simple: Consider a random coloring. The probability that an arbitrary set is monochromatic is . By a union bound, the probability that there exist a monochromatic set is less than . Therefore, there exists a good coloring.

Erdős (1964) showed the existence of an n-uniform hypergraph with hyperedges which does not have property B (i.e., does not have a 2-coloring in which all hyperedges are bichromatic), establishing an upper bound.

Schmidt (1963) proved that every collection of at most sets of size n has property B. Erdős and Lovász conjectured that . Beck in 1978 improved the lower bound to , where is an arbitrary small positive number. In 2000, Radhakrishnan and Srinivasan improved the lower bound to . They used a clever probabilistic algorithm.

See also

Related Research Articles

In combinatorial mathematics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling of a sufficiently large complete graph. To demonstrate the theorem for two colours, let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices.

Hypergraph Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

In combinatorics, the Erdős–Ko–Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is a theorem on intersecting set families.

In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.

In combinatorics, a Helly family of order k is a family of sets in which every minimal subfamily with an empty intersection has k or fewer sets in it. Equivalently, every finite subfamily such that every k-fold intersection is non-empty has non-empty total intersection. The k-Helly property is the property of being a Helly family of order k.

Erdős–Faber–Lovász conjecture

In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:

In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive probability that none of the events will occur. The Lovász local lemma allows one to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the probabilistic method, in particular to give existence proofs.

Triangle-free graph Graph without triples of adjacent vertices

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum and combinatorics on successors of singular cardinals.

András Hajnal was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.

György Elekes was a Hungarian mathematician and computer scientist who specialized in Combinatorial geometry and Combinatorial set theory. He may be best known for his work in the field that would eventually be called Additive Combinatorics. Particularly notable was his "ingenious" application of the Szemerédi–Trotter theorem to improve the best known lower bound for the sum-product problem. He also proved that any polynomial-time algorithm approximating the volume of convex bodies must have a multiplicative error, and the error grows exponentially on the dimension. With Micha Sharir he set up a framework which eventually led Guth and Katz to the solution of the Erdős distinct distances problem.

Degeneracy (graph theory) Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph. A sequence obeying these conditions is called "graphic". The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named.

Topological graph

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.

Half graph

In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.

In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree and complete graph , the graphs with neither nor as induced subgraphs can be properly colored using only a constant number of colors. Equivalently, it asks whether the -free graphs are -bounded. It is named after András Gyárfás and David Sumner, who formulated it independently in 1975 and 1981 respectively. It remains unproven.

References

  1. Bernstein, F. (1908), "Zur theorie der trigonometrische Reihen", Leipz. Ber., 60: 325–328.
  2. Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN   0-444-87916-1, MR   0859549
  3. Beck, J. (1978), "On 3-chromatic hypergraphs", Discrete Mathematics, 24 (2): 127–137, doi: 10.1016/0012-365X(78)90191-7 , MR   0522920

Further reading