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.[1][2]
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 {1,2,3,4,5,6,7} and 7 edges {123, 145, 167, 246, 257, 347, 356}.
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 {1,2,3,4,5,6} and 4 edges {123, 154, 624, 653}. It is a tripartite hypergraph with sides {1,6},{2,5},{3,4} (which are exactly the neighbors of the removed vertex 7). It is also called the Pasch hypergraph, due to its connection with Pasch's axiom.[3]:4
It is a 2-regular hypergraph (each vertex is in exactly two edges), and its maximum matching is of size 1 (every two of its edges intersect).
Combinatorics of dual affine planes
A finite projective plane of order n has n + 1 points on every line (n + 1 = r in the hypergraph description). There are n2 + n + 1 total points and an equal number of lines. Each point is on n + 1 lines. Every two distinct points lie on a unique line and every two distinct lines meet at a unique point.
By removing a point and all the lines that pass through that point, the configuration that is left has n2 + n points, n2 lines, each point is on n lines and each line contains n + 1 points. Each pair of distinct lines still meet at a unique point, but two distinct points are on at most one line. This dual affine plane is thus a configuration of type ((n2 + n)n (n2)n + 1).
The points can be partitioned into n + 1 sets of n points apiece, where no two points in the same partition set are joined by a line. These sets are the analogs of classes of parallel lines in an affine plane, and some authors refer to the points in a partition piece as parallel points in keeping with the dual nature of the structure.[4]
Projective planes constructed from finite fields (Desarguesian planes) have automorphism groups that act transitively on the points of the plane, so for these planes the point removed to form the dual affine plane is immaterial, the results of choosing different points are isomorphic. However, there do exist non-Desarguesian planes and the choice of point to remove in them may result in non-isomorphic dual affine planes having the same parameters.
An affine plane is obtained by removing a line and all the points on that line from a projective plane. Since a projective plane is a self-dual configuration, the dual configuration of an affine plane is obtained from a projective plane by removing a point and all the lines through that point. Hence the name of this configuration.
Hypergraph properties
It is known that the projective plane of order r-1 exists whenever r-1 is a prime power; hence the same is true for the TPP.
The finite projective plane of order r-1 contains r2-r+1 vertices and r2-r+1 edges; hence the TPP of order r-1 contains r2-r vertices and r2-2r+1 edges.
The TPP of order r-1 is an r-partite hypergraph: its vertices can be partitioned into r parts such that each hyperedge contains exactly one vertex of each part. For example, in the TPP of order 2, the 3 parts are {1,6}, {2,5} and {3,4}. In general, each of the r parts contains r-1 vertices.
Each edge in a TPP intersects every other edge. Therefore, its maximum matching size is 1:
.
On the other hand, covering all edges of the TPP requires all r-1 vertices of one of the parts. Therefore, its minimum vertex-cover size is r-1:
The minimum fractional vertex-cover size of the TPP is r-1 too: assigning a weight of 1/r to each vertex (which is a vertex-cover since each hyperedge contains r vertices) yields a fractional cover of size (r2-r)/r=r-1.
Its maximum fractional matching size of the is r-1 too: assigning a weight of 1/(r-1) to each hyperedge (which is a matching since each vertex is contained in r-1 edges) yields a fractional matching of size (r2-2r+1)/(r-1)=r-1. Therefore:[7]
.
Note that the above fractional matching is perfect, since its size equals the number of vertices in each part of the r-partite hypergraph. However, there is no perfect matching, and moreover, the maximum matching size is only 1. This is in contrast to the situation in bipartite graphs, in which a perfect fractional matching implies the existence of a perfect matching.
Design-theoretic aspects
Dual affine planes can be viewed as a point residue of a projective plane,[8] a 1-design,[9] and, more classically, as a tactical configuration.[10]
Since they are not pairwise balanced designs (PBDs), they have not been studied extensively from the design-theoretic viewpoint. However, tactical configurations are central topics in geometry, especially finite geometry.
↑ Tuza (1983). "Ryser's conjecture on transversals of r-partite hypergraphs". Ars Combinatorica.
↑ Abu-Khazneh, Ahmad; Barát, János; Pokrovskiy, Alexey; Szabó, Tibor (2018-07-12). "A family of extremal hypergraphs for Ryser's conjecture". arXiv:1605.06361 [math.CO].
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 the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
In finite geometry, the Fano plane is the finite projective plane of order 2. It is the finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. The standard notation for this plane, as a member of a family of projective spaces, is PG(2, 2) where PG stands for "projective geometry", the first parameter is the geometric dimension and the second parameter is the order.
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 mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore all the properties of this geometry except for the relation of which points are on which lines for all points and lines. What is left is the incidence structure of the Euclidean plane.
In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An incidence structure is what is obtained when all other concepts are removed and all that remains is the data about which points lie on which lines. Even with this severe limitation, theorems can be proved and interesting facts emerge concerning this structure. Such fundamental results remain valid when additional concepts are added to form a richer geometry. It sometimes happens that authors blur the distinction between a study and the objects of that study, so it is not surprising to find that some authors refer to incidence structures as incidence geometries.
In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), 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.
In mathematics, specifically projective geometry, a configuration in the plane consists of a finite set of points, and a finite arrangement of lines, such that each point is incident to the same number of lines and each line is incident to the same number of points.
Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.
In geometry, specifically projective geometry, a blocking set is a set of points in a projective plane that every line intersects and that does not contain an entire line. The concept can be generalized in several ways. Instead of talking about points and lines, one could deal with n-dimensional subspaces and m-dimensional subspaces, or even more generally, objects of type 1 and objects of type 2 when some concept of intersection makes sense for these objects. A second way to generalize would be to move into more abstract settings than projective geometry. One can define a blocking set of a hypergraph as a set that meets all edges of the hypergraph.
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
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.
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.
In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.
In combinatorics, Hall-type theorems for hypergraphs are several generalization of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.
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.
In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs.
In graph theory, there are two related properties of a hypergraph that are called its "width". Given a hypergraph H =, we say that a set K of edges pins another set F of edges if every edge in F intersects some edge in K. Then:
In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph, which is the smallest index k such that all reduced homological groups up to and including k are trivial. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.
In graph theory, a d-interval hypergraph is a kind of a hypergraph constructed using intervals of real lines. The parameter d is a positive integer. The vertices of a d-interval hypergraph are the points of d disjoint lines. The edges of the graph are d-tuples of intervals, one interval in every real line.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
