|
Polynomial Method In Combinatorics
In mathematics, the polynomial method is an algebraic approach to combinatorics problems that involves capturing some combinatorial structure using polynomials and proceeding to argue about their algebraic properties. Recently, the polynomial method has led to the development of remarkably simple solutions to several long-standing open problems. The polynomial method encompasses a wide range of specific techniques for using polynomials and ideas from areas such as algebraic geometry to solve combinatorics problems. While a few techniques that follow the framework of the polynomial method, such as Alon's Combinatorial Nullstellensatz, have been known since the 1990s, it was not until around 2010 that a broader framework for the polynomial method has been developed. Mathematical overview Many uses of the polynomial method follow the same high-level approach. The approach is as follows: * Embed some combinatorial problem into a vector space. * Capture the hypotheses of the proble ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science. Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ''ad hoc'' solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is gra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Restricted Sumset
In additive number theory and combinatorics, a restricted sumset has the form :S=\, where A_1,\ldots,A_n are finite nonempty subsets of a field ''F'' and P(x_1,\ldots,x_n) is a polynomial over ''F''. If P is a constant non-zero function, for example P(x_1,\ldots,x_n)=1 for any x_1,\ldots,x_n, then S is the usual sumset A_1+\cdots+A_n which is denoted by nA if A_1=\cdots=A_n=A. When :P(x_1,\ldots,x_n) = \prod_ (x_j-x_i), ''S'' is written as A_1\dotplus\cdots\dotplus A_n which is denoted by n^ A if A_1=\cdots=A_n=A. Note that , ''S'', > 0 if and only if there exist a_1\in A_1,\ldots,a_n\in A_n with P(a_1,\ldots,a_n)\not=0. Cauchy–Davenport theorem The Cauchy–Davenport theorem, named after Augustin Louis Cauchy and Harold Davenport, asserts that for any prime ''p'' and nonempty subsets ''A'' and ''B'' of the prime order cyclic group \mathbb/p\mathbb we have the inequalityGeroldinger & Ruzsa (2009) pp.141–142 :, A+B, \ge \min\ where A+B := \, i.e. we're using modu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kakeya Set
In mathematics, a Kakeya set, or Besicovitch set, is a set of points in Euclidean space which contains a unit line segment in every direction. For instance, a disk of radius 1/2 in the Euclidean plane, or a ball of radius 1/2 in three-dimensional space, forms a Kakeya set. Much of the research in this area has studied the problem of how small such sets can be. Besicovitch showed that there are Besicovitch sets of measure zero. A Kakeya needle set (sometimes also known as a Kakeya set) is a (Besicovitch) set in the plane with a stronger property, that a unit line segment can be rotated continuously through 180 degrees within it, returning to its original position with reversed orientation. Again, the disk of radius 1/2 is an example of a Kakeya needle set. Kakeya needle problem The Kakeya needle problem asks whether there is a minimum area of a region D in the plane, in which a needle of unit length can be turned through 360°. This question was first posed, for Convex set, convex ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Homogeneous Polynomial
In mathematics, a homogeneous polynomial, sometimes called quantic in older texts, is a polynomial whose nonzero terms all have the same degree. For example, x^5 + 2 x^3 y^2 + 9 x y^4 is a homogeneous polynomial of degree 5, in two variables; the sum of the exponents in each term is always 5. The polynomial x^3 + 3 x^2 y + z^7 is not homogeneous, because the sum of exponents does not match from term to term. The function defined by a homogeneous polynomial is always a homogeneous function. An algebraic form, or simply form, is a function defined by a homogeneous polynomial. A binary form is a form in two variables. A ''form'' is also a function defined on a vector space, which may be expressed as a homogeneous function of the coordinates over any basis. A polynomial of degree 0 is always homogeneous; it is simply an element of the field or ring of the coefficients, usually called a constant or a scalar. A form of degree 1 is a linear form. A form of degree 2 is a quadratic fo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schwartz–Zippel Lemma
In mathematics, the Schwartz–Zippel lemma (also called the DeMillo–Lipton–Schwartz–Zippel lemma) is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomial is the 0-polynomial (or identically equal to 0). It was discovered independently by Jack Schwartz, Richard Zippel, and Richard DeMillo and Richard J. Lipton, although DeMillo and Lipton's version was shown a year prior to Schwartz and Zippel's result. The finite field version of this bound was proved by Øystein Ore in 1922.Ö. Ore, Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I (1922), no. 7, 15 pages. Statement and proof of the lemma Theorem 1 (Schwartz, Zippel). ''Let'' : P\in F _1,x_2,\ldots,x_n/math> ''be a non-zero polynomial of total degree'' ''over a field F. Let S be a finite subset of F and let'' ''be selected at random independently and uniformly from S. Then'' : \Pr (r_1,r_2,\ldots,r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Erdős Distinct Distances Problem
In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946 and almost proven by Larry Guth and Nets Katz in 2015. The conjecture In what follows let denote the minimal number of distinct distances between points in the plane, or equivalently the smallest possible cardinality of their distance set. In his 1946 paper, Erdős proved the estimates :\sqrt-1/2\leq g(n)\leq c n/\sqrt for some constant c. The lower bound was given by an easy argument. The upper bound is given by a \sqrt\times\sqrt square grid. For such a grid, there are O( n/\sqrt) numbers below ''n'' which are sums of two squares, expressed in big O notation; see Landau–Ramanujan constant. Erdős conjectured that the upper bound was closer to the true value of ''g''(''n''), and specifically that (using big Omega notation) g(n) = \Omega(n^c) holds for every . Partial results Paul Erdős ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Szemerédi–Trotter Theorem
The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given points and lines in the Euclidean plane, the number of incidences (''i.e.'', the number of point-line pairs, such that the point lies on the line) is O \left ( n^ m^ + n + m \right ). This bound cannot be improved, except in terms of the implicit constants. As for the implicit constants, it was shown by János Pach, Radoš Radoičić, Gábor Tardos, and Géza Tóth that the upper bound 2.5n^ m^ + n + m holds. Since then better constants are known due to better crossing lemma constants; the current best is 2.44. On the other hand, Pach and Tóth showed that the statement does not hold true if one replaces the coefficient 2.5 with 0.42. An equivalent formulation of the theorem is the following. Given points and an integer , the number of lines which pass through at least of the points is O \left( \frac + \frac \right ). The original proof of Endre Szemeréd ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ham Sandwich Theorem
In mathematical measure theory, for every positive integer the ham sandwich theorem states that given measurable "objects" in -dimensional Euclidean space, it is possible to divide each one of them in half (with respect to their measure, e.g. volume) with a single -dimensional hyperplane. This is even possible if the objects overlap. It was proposed by Hugo Steinhaus and proved by Stefan Banach (explicitly in dimension 3, without taking the trouble to state the theorem in the -dimensional case), and also years later called the Stone–Tukey theorem after Arthur H. Stone and John Tukey. Naming The ham sandwich theorem takes its name from the case when and the three objects to be bisected are the ingredients of a ham sandwich. Sources differ on whether these three ingredients are two slices of bread and a piece of ham , bread and cheese and ham , or bread and butter and ham . In two dimensions, the theorem is known as the pancake theorem to refer to the flat nature of the two ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete & Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geometry. Abstracting and indexing The journal is indexed in: * ''Mathematical Reviews'' * ''Zentralblatt MATH'' * ''Science Citation Index'' * ''Current Contents''/Engineering, Computing and Technology Notable articles The articles by Gil Kalai with a proof of a subexponential upper bound on the diameter of a polyhedron and by Samuel Ferguson on the Kepler conjecture, both published in Discrete & Computational geometry, earned their author the Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e .... References External link ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cap Set
In affine geometry, a cap set is a subset of \mathbb_3^n (an n-dimensional affine space over a three-element field) with no three elements in a line. The cap set problem is the problem of finding the size of the largest possible cap set, as a function of n.. The first few cap set sizes are 1, 2, 4, 9, 20, 45, 112, ... . Cap sets may be defined more generally as subsets of finite affine or projective spaces with no three in line, where these objects are simply called caps. The "cap set" terminology should be distinguished from other unrelated mathematical objects with the same name, and in particular from sets with the compact absorption property in function spaces as well as from compact convex co-convex subsets of a convex set. Example An example of cap sets comes from the card game Set, a card game in which each card has four features (its number, symbol, shading, and color), each of which can take one of three values. The cards of this game can be interpreted as representing p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Advances In Mathematics
''Advances in Mathematics'' is a peer-reviewed scientific journal covering research on pure mathematics. It was established in 1961 by Gian-Carlo Rota. The journal publishes 18 issues each year, in three volumes. At the origin, the journal aimed at publishing articles addressed to a broader "mathematical community", and not only to mathematicians in the author's field. Herbert Busemann writes, in the preface of the first issue, "The need for expository articles addressing either all mathematicians or only those in somewhat related fields has long been felt, but little has been done outside of the USSR. The serial publication ''Advances in Mathematics'' was created in response to this demand." Abstracting and indexing The journal is abstracted and indexed in: * |
Journal Of Combinatorial Theory
The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applications of combinatorics. ''Series B'' is concerned primarily with graph and matroid theory. The two series are two of the leading journals in the field and are widely known as ''JCTA'' and ''JCTB''. The journal was founded in 1966 by Frank Harary and Gian-Carlo Rota.They are acknowledged on the journals' title pages and Web sites. SeEditorial board of JCTA Originally there was only one journal, which was split into two parts in 1971 as the field grew rapidly. An electronic, [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
