|
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] |
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] |
Kőnig's Theorem (graph Theory)
In the mathematical area of graph theory, Kőnig's theorem, proved by , describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs. Setting A vertex cover in a graph is a set of vertices that includes at least one endpoint of every edge, and a vertex cover is ''minimum'' if no other vertex cover has fewer vertices. A matching in a graph is a set of edges no two of which share an endpoint, and a matching is ''maximum'' if no other matching has more edges. It is obvious from the definition that any vertex-cover set must be at least as large as any matching set (since for every edge in the matching, at least one vertex is needed in the cover). In particular, the minimum vertex cover set is at least as large as the maximum matching set. Kőnig's theorem states that, in any bipartite graph, the minimum vertex c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ron Aharoni
Ron Aharoni ( he, רון אהרוני ) (born 1952) is an Israeli mathematician, working in finite and infinite combinatorics. Aharoni is a professor at the Technion – Israel Institute of Technology, where he received his Ph.D. in mathematics in 1979. With Nash-Williams and Shelah he generalized Hall's marriage theorem by obtaining the right transfinite conditions for infinite bipartite graphs. He subsequently proved the appropriate versions of the Kőnig theorem and the Menger theorem for infinite graphs (the latter with Eli Berger). Aharoni is the author of several nonspecialist books; the most successful is '' Arithmetic for Parents'', a book helping parents and elementary school teachers in teaching basic mathematics. He also wrote a book on the connections between ''Mathematics, poetry and beauty'' and on philosophy, ''The Cat That is not There''. His book, "Man detaches meaning", is on a mechanism common to jokes and poetry. His last to date book iCircularity: A Common Se ... [...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] |
Penny Haxell
Penelope Evelyn Haxell is a Canadian mathematician who works as a professor in the department of combinatorics and optimization at the University of Waterloo. Her research interests include extremal combinatorics and graph theory. Education and career Haxell earned a bachelor's degree in 1988 from the University of Waterloo, and completed a doctorate in 1993 from the University of Cambridge under the supervision of Béla Bollobás. Since then, she has worked at the University of Waterloo, where she was promoted to full professor in 2004. Research Haxell's research accomplishments include results on the Szemerédi regularity lemma, hypergraph generalizations of Hall's marriage theorem (see Haxell's matching theorem), fractional graph packing problems, and strong coloring of graphs. Recognition Haxell was the 2006 winner of the Krieger–Nelson Prize of the Canadian Mathematical Society The Canadian Mathematical Society (CMS) (french: Société mathématique du Canada) is an a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fractional Matching
In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices. Definition Given a graph ''G'' = (''V'', ''E''), a fractional matching in ''G'' is a function that assigns, to each edge ''e'' in ''E'', a fraction ''f''(''e'') in , 1 such that for every vertex ''v'' in ''V'', the sum of fractions of edges adjacent to ''v'' is at most 1: \forall v\in V: \sum_f(e)\leq 1 A matching in the traditional sense is a special case of a fractional matching, in which the fraction of every edge is either 0 or 1: ''f''(''e'') = 1 if ''e'' is in the matching, and ''f''(''e'') = 0 if it is not. For this reason, in the context of fractional matchings, usual matchings are sometimes called ''integral matchings''. The size of an integral matching is the number of edges in the matching, and the matching number \nu(G) of a graph ''G'' is the largest size of a matching in ''G''. A ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
