Name
Abstract | ||
|---|---|---|
An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct with the result that they can be considered as sets. For a sequence S, subsequence S', and set T, |T ∩ S| denotes the number of terms x of S with x ∈ T, and |S| denotes the length of S, and S \ S' denotes the subsequence of S obtained by deleting all terms in S'. We first prove the following two additive number theory results.(1) Let S be a finite sequence of elements from an abelian group G. If S has an n-set partition, A = A1, ..., An, such that |Σi=1n Ai| ≥ Σi=1n |Ai| - n + 1, then there exists a subsequence S' of S, with length |S'| ≤ max{|S - n + 1, 2n}, and with an n-set partition, A' = A'1, ..., A'n, such that |Σi=1n A'i| ≥ Σi=1n |Ai| - n + 1. Furthermore, if ||Ai| - |Aj|| ≤ 1 for all i and j, or if |Ai| ≥ 3 for all i, then A'i ⊆ Ai.(2) Let S be a sequence of elements from a finite abelian group G of order m, and suppose there exist a, b ∈ G such that |(G \ {a, b}) ∩ S| ≤ ⌊m/2⌋. If |S| ≥ 2m - 1, then there exists an m-term zero-sum subsequence S' of S with |{a} ∩ S'| ≥ ⌊ m/2 ⌋ or |{b} ∩ S'| ≥ ⌊ m/2 ⌋.Let H be a connected, finite m-uniform hypergraph, and let f(H) (let fzs(H)) be the least integer n such that for every 2-coloring (coloring with the elements of the cyclic group Zm) of the vertices of the complete m-uniform hypergraph Knm, there exists a subhypergraph K isomorphic to H such that every edge in K is monochromatic (such that for every edge e in K the sum of the colors on e is zero). As a corollary to the above theorems, we show that if every subhypergraph H' of H contains an edge with at least half of its vertices monovalent in H', or if H consists of two intersecting edges, then fzs(H) = f(H). This extends the Erdös-Ginzburg-Ziv Theorem, which is the case when H is a single edge. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.ejc.2004.07.005 | Eur. J. Comb. |
Keywords | Field | DocType |
abelian group,n nonempty subsequence,n-set partition,intersecting edge,edge e,m-term zero-sum subsequence,cyclic group,subhypergraph h,single edge,finite sequence,s-ginzburg-ziv theorem,additive number theory | Discrete mathematics,Abelian group,Combinatorics,Disjoint sets,Vertex (geometry),Cyclic group,Hypergraph,Partition (number theory),Subsequence,Mathematics,Additive number theory | Journal |
Volume | Issue | ISSN |
26 | 8 | 0195-6698 |
Citations | PageRank | References |
3 | 0.54 | 9 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Grynkiewicz | 1 | 42 | 10.33 |