Sample of hypergraph: X = {v₁,v₂,v₃,v₄,v₅,v₆,v₇}, E = {e₁,e₂,e₃,e₄} = {{v₁,v₂,v₃},{v₂,v₃}, {v₃,v₅,v₆},{v₄}}.

In mathematics, a hypergraph is a generalization of a graph, where edges can connect any number of vertices. Formally, a hypergraph is a pair (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. Therefore, E is a subset of , where is the power set of X. While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. Image File history File links No higher resolution available. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... This article just presents the basic definitions. ... In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ...

A hypergraph is also called a set system or a family of sets drawn from the universal set X. Hypergraphs can be viewed as incidence structures and vice versa. // Definition In mathematics, in particular in combinatorics, an incidence structure is a triple where is the set of points, is the set of lines and is the incidence relation. ...

Unlike graphs, hypergraphs are difficult to draw on paper, so they tend to be studied using the nomenclature of set theory rather than the more pictorial descriptions (like 'trees','forests' and 'cycles') of graph theory. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...

Theorems

Many theorems involving graphs also hold for hypergraphs. Ramsey's theorem is a typical example. Some methods for studying symmetries of graphs extend to hypergraphs. For instance, a hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge. A hypergraph isomorphism is a homomorphism that is invertible. A hypergraph automorphism is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraph H (= (X, E)) is a group under composition, called the automorphism group of the hypergraph and written Aut(H). The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms. Look up theorem in Wiktionary, the free dictionary. ... In combinatorics, Ramseys theorem states that in colouring a large complete graph (that is a simple graph, where an edge connects every pair of vertices), one will find complete subgraphs all of the same colour. ... In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ... In mathematics, an automorphism is an isomorphism from a mathematical object to itself. ... This picture illustrates how the hours in a clock form a group. ... In mathematics, an automorphism is an isomorphism from a mathematical object to itself. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ...

A transversal or hitting set of a hypergraph H = (X, E) is a set that has nonempty intersection with every edge. A transversal T is called minimal if no proper subset of T is a transversal. The transversal hypergraph of H is the hypergraph (X, F) whose edge set F consists of all minimal transversals of H. Computing the transversal hypergraph has applications in machine learning and other fields of computer science. In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ... Given a collection C of disjoint sets, a transversal is a set containing exactly one member of each of them. ... As a broad subfield of artificial intelligence, machine learning is concerned with the design and development of algorithms and techniques that allow computers to learn. At a general level, there are two types of learning: inductive, and deductive. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...

A hypergraph H is called k-uniform or a k-hypergraph if every edge has cardinality k. A graph is just a 2-uniform hypergraph. The degree d(v) of a vertex v is the number of edges that contain it. H is k-regular if every vertex has degree k.

Let and . Every hypergraph has an incidence matrix A = (a_ij) where

The transpose A^t of the incidence matrix defines a hypergraph H ^* = (V ^* ,E ^* ) called the dual of H, where V ^* is an m-element set and E ^* is an n-element set of subsets of V ^* . For and if and only if a_ij = 1. The dual of a uniform hypergraph is regular and vice-versa. Considering duals often leads to discoveries. In linear algebra, the transpose of a matrix A is another matrix AT (also written Atr, tA, or A′) created by any one of the following equivalent actions: write the rows of A as the columns of AT write the columns of A as the rows of AT reflect A... In optics one considers angles of incidence. ...

Hypergraph colouring

Hypergraph colouring is defined as follows. Be H = (V,E) a hypergraph such that . We claim that is a proper colouring of H if and only if, for all , there exists such that .

See also

• Erdős-Ko-Rado theorem
• Almost disjoint sets
• Disjoint sets
• Partition of a set
• Finite intersection property
• Abstract simplicial complex
• Incidence structure
• Kruskal-Katona theorem

This article incorporates material from hypergraph on PlanetMath, which is licensed under the GFDL. In combinatorial mathematics, the Erdős-Ko-Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is the following. ... In mathematics, two sets are almost disjoint if their intersection is small in some sense. ... In mathematics, two sets are said to be disjoint if they have no element in common. ... A partition of U into 6 blocks: an Euler diagram representation. ... In topology, the finite intersection property is a property of a collection of subsets of a set X. A collection has this property if the intersection over any finite subcollection of the collection is nonempty. ... In mathematics, given a universal set , and , a family of sets over , is an abstract simplicial complex if the following is true: for each , if then for each subset it follows that . ... // Definition In mathematics, in particular in combinatorics, an incidence structure is a triple where is the set of points, is the set of lines and is the incidence relation. ... The Kruskal–Katona theorem is a combinatorial theorem about uniform hypergraphs. ... PlanetMath is a free, collaborative, online mathematics encyclopedia. ...