Barycentric-sum problem


Barycentric-sum problem

Combinatorial number theory deals with number theoretic problems which involve combinatorial ideas in their formulations or solutions. Paul Erdős is the main founder of this branch of number theory. Typical topics include covering system, zero-sum problems, various restricted sumsets, and arithmetic progressions in a set of integers. Algebraic or analytic methods are powerful in this field.

In combinatorial number theory, the barycentric-sum problems are questions that can be answered using combinatorial techniques. The context of barycentric-sum problems are the barycentric sequences.

Example

Let Z_n be the cyclic group of integers modulo "n". Let "S" be a sequence of elements of Z_n, where the repetition of elements is allowed. Let |S| be the length of "S". A sequence S subseteq Z_n with |S| geq 2 is barycentric or has abarycentric-sum if it contains one element a_j such that sumlimits_ {a_i in S} a_i=|S|a_j.

Informally, if S contains one element a_j, which is the ”average” of its terms. A barycentric sequence of length t is called a t-barycentric sequence. Moreover when "S" is a set, the term barycentric set is used instead of barycentric sequence. For example, the set {0,1,2,3,4} subseteq Z_8 is 5-barycentric with barycenter 2, however the set {0,2,3,4,5} subseteq Z_8 is not 5-barycentric. The barycentric-sum problem consist in finding the smallest integer "t" such that any sequence of length "t" contains a "k"-barycentric sequence for some given "k".The study of the existence of such t related with k and the study of barycentric constants are part of the barycentric-sum problems. It has been introduced by Ordaz, [C. Delorme, S. González, O. Ordaz and M.T. Varela. Barycentric sequences and barycentric Ramsey numbers stars, Discrete Math. 277(2004)45–56.] [C. Delorme, I. Márquez, O. Ordaz and A. Ortuño. Existence conditionfor barycentric sequences, Discrete Math. 281(2004)163–172.] inspired in a theorem of Hamidoune [Y. O. Hamidoune. On weighted sequences sums, Combinatorics, Probabilityand Computing 4(1995) 363–367.] : every sequence of leght n + k - 1 in Z_n contains a k-barycentric sequence. Notice that a "k"-barycentric sequence in Z_n, with k a multiple of n is a sequence with zero-sum . The zero-sum problem on sequences started in 1961 with the Erdős, Ginzburg and Ziv theorem: every sequence of length 2n-1 in an abelian group of order "n", contains an "n"-subsequence with zero-sum. [Y. Caro. Zero-sum problems: a survey. Discrete Math. 152 (1996) 93–113.] [P. Erdős, A. Ginzburg and A. Ziv. Theorem in the additive number theory, Bull. Res. Council Israel 10F (1961) 41–43.] [C. Flores and O. Ordaz. On sequences with zero sum in abelian group. Volume in homage to Dr. Rodolfo A. Ricabarra (Spanish), 99-106, Vol. Homenaje, 1, Univ. Nac. del Sur, Bahia Blanca, 1995.] [W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: A survey. Expositiones Mathematicae 24 (2006), n. 4, 337–369.] [D. J. Grynkiewicz, O. Ordaz, M.T. Varela and F. Villarroel, On the Erd˝os-Ginzburg-Ziv Inverse Theorems. Acta Arithmetica. 129 (2007)307–318. 2] [Y. O. Hamidoune, O. Ordaz and A. Ortuño. On a combinatorial theorem of Erdós-Ginzburg-Ziv. Combinatorics, Probability and Computing 7 (1998)403–412.] [O. Ordaz and D. Quiroz, Representation of group elements as subsequencessums, To appear in Discrete Math.]

Barycentric-sum problems have been defined in general for finite abelian groups. However, most of the main results obtained up to now are in Z_n.

The barycentric constants introduced by Ordaz are [S. González, L. González and O. Ordaz. Barycentric Ramsey numbers for small graphs, To appear in Bulletin of the Malaysan MathematicalSciences Society.] [L. González, I. Márquez, O. Ordaz and D. Quiroz, Constrained and generalized barycentric Davenport constants, Divulgaciones Matemáticas 15 No. 1 (2007)11–21.] C. Guia, F. Losavio, O. Ordaz M.T. Varela and F. Villarroel, Barycentric Davenport constants. To appear in Divulgaciones Matemáticas.] [O. Ordaz, M.T. Varela and F. Villarroel. k-barycentric Olson constant.To appear in Mathematical Reports.] [O. Ordaz and D. Quiroz, Barycentric-sum problem: a survey. Divulgaciones Matemáticas 15 No. 2 (2007)193–206.] : "k"-barycentric Olson constant, "k"-barycentric Davenport constant, barycentric Davenport constant, generalized barycentric Davenport constant, constrained barycentric Davenport constant. This constants are related to the Davenport constant [C. Delorme, O. Ordaz and D. Quiroz. Some remarks on Davenport constant, Discrete Math. 237(2001)119–128.] i.e. the smallest integer "t" such that any "t"-sequence contains a subsequence with zero-sum. Moreover related to the classical Ramsey numbers , the barycentric Ramsey numbers are introduced. An overview of the results computed manually or automatically are presented.L. González, F. Losavio, O. Ordaz, M.T. Varela and F. Villarroel. Barycentric Integers sequences. Sumited to Expositiones Mathematicae.] The implemented algorithms are written in C. [F. Villarroel,Tesis Doctoral en Matemática. La constante de Olson k baricéntrica y un teorema inverso de Erdős-Ginzburg-Ziv. Facultad de Ciencias. Universidad Central de Venezuela, (2008).]

References

External links

* [http://www.emis.de/journals/DM/ Divulgacions Matemáticas (Spanish)]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Barycentric coordinates (mathematics) — In mathematics, barycentric coordinates are coordinates defined by the vertices of a simplex (a triangle, tetrahedron, etc). Barycentric coordinates are a form of homogeneous coordinates.Let x 1, ..., x n be the vertices of a simplex in a vector… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Vector space — This article is about linear (vector) spaces. For the structure in incidence geometry, see Linear space (geometry). Vector addition and scalar multiplication: a vector v (blue) is added to another vector w (red, upper illustration). Below, w is… …   Wikipedia

  • Coordinate time — In the theory of relativity, it is convenient to express results in terms of a spacetime coordinate system relative to an implied observer. In many (but not all) coordinate systems, an event is specified by one time coordinate and three spatial… …   Wikipedia

  • Simplex — For other uses, see Simplex (disambiguation). A regular 3 simplex or tetrahedron In geometry, a simplex (plural simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n… …   Wikipedia

  • Newton polynomial — In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation polynomial for a given set of data points in the Newton form. The Newton polynomial is sometimes called Newton s… …   Wikipedia

  • Mass point geometry — Mass point geometry, colloquially known as mass points, is a geometry problem solving technique which applies the physical principle of the center of mass to geometry problems involving triangles and intersecting cevians.[1] All problems that can …   Wikipedia

  • Time dilation — This article is about a concept in physics. For the concept in sociology, see time displacement. In the theory of relativity, time dilation is an observed difference of elapsed time between two events as measured by observers either moving… …   Wikipedia

  • Time — This article is about the measurement. For the magazine, see Time (magazine). For other uses, see Time (disambiguation). The flow of sand in an hourglass can be used to keep track of elapsed time. It also concretely represents the present as… …   Wikipedia

  • Nonlinear dimensionality reduction — High dimensional data, meaning data that requires more than two or three dimensions to represent, can be difficult to interpret. One approach to simplification is to assume that the data of interest lies on an embedded non linear manifold within… …   Wikipedia