|
Ryser's Conjecture
In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs. This conjecture first appeared in 1971 in the Ph.D. thesis of J. R. Henderson, whose advisor was Herbert John Ryser. Preliminaries A matching in a hypergraph is a set of hyperedges such that each vertex appears in at most one of them. The largest size of a matching in a hypergraph ''H'' is denoted by \nu(H). A transversal (or vertex cover) in a hypergraph is a set of vertices such that each hyperedge contains at least one of them. The smallest size of a transversal in a hypergraph ''H'' is denoted by \tau(H). For every ''H'', \nu(H)\leq \tau(H), since every cover must contain at least one point from each edge in any matching. If H is ''r''-uniform (each hyperedge has exactly ''r'' vertices), then \tau(H) \leq r\cdot \nu(H), since the union of the edges from any maximal matching is a set of at most ''rv'' vertices that meets every edge. T ... [...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] |
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] |
Truncated Projective Plane
In geometry, a truncated projective plane (TPP), also known as a dual affine plane, is a special kind of a hypergraph or geometric configuration that is constructed in the following way. * Take a finite projective plane. * Remove one of the points (vertices) in the plane. * Remove all lines (edges) containing that point. These objects have been studied in many different settings, often independent of one another, and so, many terminologies have been developed. Also, different areas tend to ask different types of questions about these objects and are interested in different aspects of the same objects. Example: the Pasch hypergraph Consider the Fano plane, which is the projective plane of order 2. It has 7 vertices and 7 edges . It can be truncated e.g. by removing the vertex 7 and the edges containing it. The remaining hypergraph is the TPP of order 2. It has 6 vertices and 4 edges . It is a tripartite hypergraph with sides ,, (which are exactly the neighbors of the removed ve ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Projective Plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that do not intersect. A projective plane can be thought of as an ordinary plane equipped with additional "points at infinity" where parallel lines intersect. Thus ''any'' two distinct lines in a projective plane intersect at exactly one point. Renaissance artists, in developing the techniques of drawing in perspective, laid the groundwork for this mathematical topic. The archetypical example is the real projective plane, also known as the extended Euclidean plane. This example, in slightly different guises, is important in algebraic geometry, topology and projective geometry where it may be denoted variously by , RP2, or P2(R), among other notations. There are many other projective planes, both infinite, such as the complex projective plane, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
