|
Combinatorial Geometry In The Plane
''Combinatorial Geometry in the Plane'' is a book in discrete geometry. It was translated from a German-language book, ''Kombinatorische Geometrie in der Ebene'', which its authors Hugo Hadwiger and Hans Debrunner published through the University of Geneva in 1960, expanding a 1955 survey paper that Hadwiger had published in '' L'Enseignement mathématique''. Victor Klee translated it into English, and added a chapter of new material. It was published in 1964 by Holt, Rinehart and Winston, and republished in 1966 by Dover Publications. A Russian-language edition, , translated by I. M. Jaglom and including a summary of the new material by Klee, was published by Nauka in 1965. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries. Topics The first half of the book provides the statements of nearly 100 propositions in the discrete geometry of the Euclidean plane, and the second half sketches t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hugo Hadwiger
Hugo Hadwiger (23 December 1908 in Karlsruhe, Germany – 29 October 1981 in Bern, Switzerland) was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography. Biography Although born in Karlsruhe, Germany, Hadwiger grew up in Bern, Switzerland.. He did his undergraduate studies at the University of Bern, where he majored in mathematics but also studied physics and actuarial science. He continued at Bern for his graduate studies, and received his Ph.D. in 1936 under the supervision of Willy Scherrer. He was for more than forty years a professor of mathematics at Bern. Mathematical concepts named after Hadwiger Hadwiger's theorem in integral geometry classifies the isometry-invariant valuations on compact convex sets in ''d''-dimensional Euclidean space. According to this theorem, any such valuation can be expressed as a linear combination of the intrinsic volumes; for instance, in two dimensions, the intrinsic volumes are the area, the perimeter, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete Geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object. Discrete geometry has a large overlap with convex geometry and computational geometry, and is closely related to subjects such as finite geometry, combinatorial optimization, digital geometry, discrete differential geometry, geometric graph theory, toric geometry, and combinatorial topology. History Although polyhedra and tessellations had been studied for many years by people such as Kepler and Cauchy, modern discrete geometry has its origins in the late 19th century. Early topics studie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Real Analysis
In mathematics, the branch of real analysis studies the behavior of real numbers, sequences and series of real numbers, and real functions. Some particular properties of real-valued sequences and functions that real analysis studies include convergence, limits, continuity, smoothness, differentiability and integrability. Real analysis is distinguished from complex analysis, which deals with the study of complex numbers and their functions. Scope Construction of the real numbers The theorems of real analysis rely on the properties of the real number system, which must be established. The real number system consists of an uncountable set (\mathbb), together with two binary operations denoted and , and an order denoted . The operations make the real numbers a field, and, along with the order, an ordered field. The real number system is the unique ''complete ordered field'', in the sense that any other complete ordered field is isomorphic to it. Intuitively, completeness means ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ramsey's Theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let and be any two positive integers. Ramsey's theorem states that there exists a least positive integer for which every blue-red edge colouring of the complete graph on vertices contains a blue clique on vertices or a red clique on vertices. (Here signifies an integer that depends on both and .) Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. This initiated the combinatorial theory now called Ramsey theory, that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of ''monochromatic subsets'', that is, subsets of connected edges of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Perfect Matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly one edge in . A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs: : In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched. A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal . A perfect matching can only occur when the graph has an even num ... [...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] |
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] |
Tarski's Plank Problem
In mathematics, Tarski's plank problem is a question about coverings of convex regions in ''n''-dimensional Euclidean space by "planks": regions between two hyperplanes. Tarski asked if the sum of the widths of the planks must be at least the minimum width of the convex region. The question was answered affirmatively by . Statement Given a convex body ''C'' in R''n'' and a hyperplane ''H'', the width of ''C'' parallel to ''H'', ''w''(''C'',''H''), is the distance between the two supporting hyperplanes of ''C'' that are parallel to ''H''. The smallest such distance (i.e. the infimum over all possible hyperplanes) is called the minimal width of ''C'', ''w''(''C''). The (closed) set of points ''P'' between two distinct, parallel hyperplanes in R''n'' is called a plank, and the distance between the two hyperplanes is called the width of the plank, ''w''(''P''). Tarski conjectured that if a convex body ''C'' of minimal width ''w''(''C'') was covered by a collection of planks, then ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sylvester–Gallai Theorem
The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944. A line that contains exactly two of a set of points is known as an ''ordinary line''. Another way of stating the theorem is that every finite set of points that is not collinear has an ordinary line. According to a strengthening of the theorem, every finite point set (not all on one line) has at least a linear number of ordinary lines. An algorithm can find an ordinary line in a set of n points in time O(n\log n). History The Sylvester–Gallai theorem was posed as a problem by . suggests that Sylvester may have been motivated by a related phenomenon in algebraic geometry, in which the inflection points of a cubic curve ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sperner's Lemma
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an simplex contains a cell whose vertices all have different colors. The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain. Sperner colorings have been used for effective computation of fixed points and in root-finding algorithms, and are applied in fair division (cake cutting) algorithms. Finding a Sperner coloring or equivalently a Brouwer fixed point is now believed to be an intractable computational problem, even in the plane, in the general case. The problem is PPAD-complete, a complexity class invented by Christos Papadimitriou. According to the Soviet ''Mathematical Encyclopaedia'' (ed. I.M. Vinogradov), a related 1929 theorem (of Knaster, Borsuk and Mazurkiewicz) had als ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Radon's Theorem
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex hulls is called a Radon point of the set. For example, in the case ''d'' = 2, any set of four points in the Euclidean plane can be partitioned in one of two ways. It may form a triple and a singleton, where the convex hull of the triple (a triangle) contains the singleton; alternatively, it may form two pairs of points that form the endpoints of two intersecting line segments. Proof and construction Consider any set X=\\subset \mathbf^d of ''d'' + 2 points in ''d''-dimensional space. Then there exists a set of multipliers ''a''1, ..., ''a''''d'' + 2, not all of which are zero, solving the system of linear equations : \sum_^ a_i x_i=0,\quad \sum_^ a_i=0, because there are ''d'' + 2 un ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Banach–Tarski Paradox
The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be put back together in a different way to yield two identical copies of the original ball. Indeed, the reassembly process involves only moving the pieces around and rotating them without changing their shape. However, the pieces themselves are not "solids" in the usual sense, but infinite scatterings of points. The reconstruction can work with as few as five pieces. An alternative form of the theorem states that given any two "reasonable" solid objects (such as a small ball and a huge ball), the cut pieces of either one can be reassembled into the other. This is often stated informally as "a pea can be chopped up and reassembled into the Sun" and called the "pea and the Sun paradox". The theorem is called a paradox because it contradicts ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
