|
Rainbow-colorable Hypergraph
In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph. Property B and 2-colorability The weakest definition of bipartiteness is also called 2-colorability. A hypergraph ''H'' = (''V'', ''E'') is called 2-colorable if its vertex set ''V'' can be partitioned into two sets, ''X'' and ''Y'', such that each hyperedge meets both ''X'' and ''Y''. Equivalently, the vertices of ''H'' can be 2-colored so that no hyperedge is monochromatic. Every bipartite graph ''G'' = (''X''+''Y'', ''E'') is 2-colorable: each edge contains exactly one vertex of ''X'' and one vertex of ''Y'', so e.g. ''X'' can be colored blue and ''Y'' can be colored yellow and no edge is monochromatic. The property of 2-colorability was first introduced by Felix Bernstein in the context of set families; therefore it is also called Property B. Exact 2-colorability A stronger definition of bipartiteness is: a hypergr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hypergraph
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. Formally, an undirected hypergraph H is a pair H = (X,E) where X is a set of elements called ''nodes'' or ''vertices'', and E is a set of non-empty subsets of X called ''hyperedges'' or ''edges''. Therefore, E is a subset of \mathcal(X) \setminus\, where \mathcal(X) is the power set of X. The size of the vertex set is called the ''order of the hypergraph'', and the size of edges set is the ''size of the hypergraph''. A directed hypergraph differs in that its hyperedges are not sets, but ordered pairs of subsets of X, with each pair's first and second entries constituting the tail and head of the hyperedge respectively. While graph edges connect only 2 nodes, hyperedges connect an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same card ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V red, each edge has endpoints of differing colors, as is required in the graph coloring problem.. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. One often writes G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denoting ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Felix Bernstein (mathematician)
Felix Bernstein (24 February 1878 in Halle, Germany – 3 December 1956 in Zürich, Switzerland), was a German Jewish mathematician known for proving in 1896 the Schröder–Bernstein theorem, a central result in set theory,In 1897 (aged 19), according to and less well known for demonstrating in 1924 the correct blood group inheritance pattern of multiple alleles at one locus through statistical analysis. Life Felix Bernstein was born in 1878 to a Jewish family of academics. His father Julius held the Chair of Physiology at the Martin Luther University of Halle-Wittenberg, and was the Director of the Physiological Institute at the University of Halle. While still in gymnasium in Halle, Bernstein heard the university seminar of Georg Cantor, who was a friend of Bernstein's father. From 1896 to 1900, Bernstein studied in Munich, Halle, Berlin and Göttingen. In the early Weimar Republic, Bernstein temporarily was Göttingen vice-chairman of the local chapter of German Demo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Property B
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''. The property gets its name from mathematician Felix Bernstein, who first introduced the property in 1908. Property B is equivalent to 2-coloring the hypergraph described by the collection ''C''. A hypergraph with property B is also called 2-colorable. 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. 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 se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hall's Marriage Theorem
In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations: * The combinatorial formulation deals with a collection of finite sets. It gives a necessary and sufficient condition for being able to select a distinct element from each set. * The graph theoretic formulation deals with a bipartite graph. It gives a necessary and sufficient condition for finding a matching that covers at least one side of the graph. Combinatorial formulation Statement Let \mathcal F be a family of finite sets. Here, \mathcal F is itself allowed to be infinite (although the sets in it are not) and to contain the same set multiple times. Let X be the union of all the sets in \mathcal F, the set of elements that belong to at least one of its sets. A transversal for F is a subset of X that can be obtained by choosing a distinct element from each set in \mathcal F. This concept can be formalized by defining a transversal to be the image of an injective function f: ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hall-type Theorems For Hypergraphs
In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others. Preliminaries Hall's marriage theorem provides a condition guaranteeing that a bipartite graph admits a perfect matching, or - more generally - a matching that saturates all vertices of . The condition involves the number of neighbors of subsets of . Generalizing Hall's theorem to hypergraphs requires a generalization of the concepts of bipartiteness, perfect matching, and neighbors. 1. Bipartiteness: The notion of a bipartiteness can be extended to hypergraphs in many ways (see bipartite hypergraph). Here we define a hypergraph as bipartite if it is ''exactly 2- colorable'', i.e., its vertices can be 2-colored such that each hyperedge contains exactly one yellow vertex. In other words, can be partitioned into two se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Balanced Hypergraph
In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph. Balanced hypergraphs were introduced by Berge as a natural generalization of bipartite graphs. He provided two equivalent definitions. Definition by 2-colorability A hypergraph ''H'' = (''V'', ''E'') is called 2-colorable if its vertices can be 2-colored so that no hyperedge is monochromatic. Every bipartite graph ''G'' = (''X''+''Y'', ''E'') is 2-colorable: each edge contains exactly one vertex of ''X'' and one vertex of ''Y'', so e.g. ''X'' can be colored blue and ''Y'' can be colored yellow and no edge is monochromatic. A hypergraph in which some hyperedges are singletons (contain only one vertex) is obviously not 2-colorable; to avoid such trivial obstacles to 2-colorability, it is common to consider hypergraphs that are essentially 2-colorable, i.e., they become 2-colorable upon deleting all their singleton hyperedges. A hypergraph is called balanced i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matching In Hypergraphs
In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph. Definition Recall that a hypergraph is a pair , where is a set of vertices and is a set of subsets of called ''hyperedges''. Each hyperedge may contain one or more vertices. A matching in is a subset of , such that every two hyperedges and in have an empty intersection (have no vertex in common). The matching number of a hypergraph is the largest size of a matching in . It is often denoted by . As an example, let be the set Consider a 3-uniform hypergraph on (a hypergraph in which each hyperedge contains exactly 3 vertices). Let be a 3-uniform hypergraph with 4 hyperedges: : Then admits several matchings of size 2, for example: : : However, in any subset of 3 hyperedges, at least two of them intersect, so there is no matching of size 3. Hence, the matching number of is 2. Intersec ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vertex Cover In Hypergraphs
In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph. An equivalent term is a hitting set: given a collection of sets, a set which intersects all sets in the collection in at least one element is called a hitting set. The equivalence can be seen by mapping the sets in the collection onto hyperedges. Another equivalent term, used more in a combinatorial context, is ''transversal''. The notions of hitting set and ''set cover'' are equivalent too. Definition Recall that a hypergraph is a pair , where is a set of ''vertices'' and is a set of subsets of called ''hyperedges''. Each hyperedge may contain one or more vertices. A vertex-cover (aka hitting set or transversal) in is set such that, for all hyperedges , it holds that . The vertex-cover number (aka transversal number) of a hypergraph is the smalles ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
