×

Zero-sum problems – a survey. (English) Zbl 0856.05068

The paper introduces basic concepts of the so-called zero-sum Ramsey theory and surveys major results in the area. In very informal terms, the problems of interest have the following general form: Suppose that the elements of a combinatorial structure are mapped into a finite group \(K\). Does there exist a substructure with the sum of the weights of its elements equal to 0 in \(K\)? The first result of this type is the celebrated Erdős-Ginzburg-Ziv theorem: Suppose \(m \geq k \geq 2\) are integers such that \(k|m\). Let \(a_1, \ldots, a_{m + k - 1}\) be a sequence of integers. Then there exists \(I \subseteq \{a_1, \dots, a_{m + k - 1}\}\) such that \(|I |= m\) and \(\sum_{i \in I} a_i \pmod k\). Another example of a zero-sum Ramsey problem appears in graph theory. The zero-sum Ramsey number \(R(H, Z_k)\) is the least integer \(t\) such that in any \(Z_k\)-coloring of the edges of the complete \(r\)-uniform hypergraph on \(t\) vertices there is a zero-sum copy of \(H\). The question is to determine \(R(H, Z_k)\). The survey discusses these two as well as many other related zero-sum problems. The survey is self-contained, comprehensive and includes an exhaustive list of references.

MSC:

05C55 Generalized Ramsey theory
05C65 Hypergraphs
11B50 Sequences (mod \(m\))
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] N. Alon, private communication and letters.
[2] N. Alon, Tools from higher algebra, in: R.L. Graham, M. Grotschel and L. Lovasz, eds, Handbook in Combinatorics (North-Holland, Amsterdam), to appear. · Zbl 0848.05073
[3] N. Alon, A. Bialostocki and Y. Caro, The extermal cases in Erdo˝s-Ginzburg-Ziv theorem, unpublished.
[4] Alon, N.; Caro, Y., On three zero-sum Ramsey-type problems, Graph theory, 17, 177-192, (1993) · Zbl 0783.05074
[5] Alon, N.; Dubiner, M., Zero-sum sets of prescribed size, (), 33-50 · Zbl 0823.11006
[6] Alon, N.; Friedland, S.; Kalai, G., Regular subgraphs of almost regular graphs, J. combin. theory ser. B, 37, 79-91, (1984) · Zbl 0527.05059
[7] Alon, N.; Friedland, S.; Kalai, G., Every 4-regular graph plus an edge contains a 3-regular subgraph, J. combin. theory ser. B, 37, 92-93, (1984) · Zbl 0546.05054
[8] Alon, N.; Kleitman, D.; Lipton, R.; Meshulam, R.; Rabin, M.; Spencer, J., Set systems with no union of cardinality o(mod m), Graphs combin., 7, 97-99, (1991) · Zbl 0762.05079
[9] N. Alon, M. Nathanson and I. Rusza, Adding distinct residue classes modulo a prime, to appear.
[10] Baker, R.C.; Schmidt, W.M., Diophantine problems in variables restricted to the values 0 and 1, J. number theory, 12, 460-486, (1980) · Zbl 0444.10013
[11] Bialostocki, A., Some combinatorial number theory aspects of Ramsey theory, Research proposal, (1989)
[12] Bialostocki, A.; Caro, Y.; Roditty, Y., On zero-sum turan numbers, Ars combin., 29A, 117-127, (1990) · Zbl 0737.05068
[13] Bialostocki, A.; Dierker, P., Zero-sum Ramsey theorems, (), 119-130 · Zbl 0695.05050
[14] Bialostocki, A.; Dierker, P., On the erdo˝s-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings, Discrete math., 110, 1-8, (1992) · Zbl 0774.05065
[15] Bialostocki, A.; Dierker, P., Zero-sum Ramsey numbers — small graphs, Ars combin., 29A, 193-198, (1990) · Zbl 0708.05039
[16] Bialostocki, A.; Dierker, P., On zero-sum Ramsey numbers — multiple copies of a graph, J. graph theory, 18, 143-151, (1994) · Zbl 0794.05081
[17] A. Bialostocki, P. Dierker and M. Lotspeich, Some developments of the Erdo˝s-Ginzburg-Ziv Theorem — II, manuscript, submitted. · Zbl 1069.11007
[18] Bialostocki, A.; Dierker, P.; Voxman, B., Some notes on the erdo˝s-Szekeres theorem, Discrete math., 91, 117-127, (1991) · Zbl 0769.52014
[19] A. Bialostocki and M. Lotspeich, Some developments of the Erdo˝s-Ginzburg-Ziv theorem — I, manuscript, submitted. · Zbl 1042.11510
[20] Bollodas, B., Extremal graph theory, (1978), Academic Press New York
[21] Borevich, Z.I.; Shafarevich, I.R., Number theory, (1966), Academic Press New York · Zbl 0145.04902
[22] Burr, S.A., Generalized Ramsey theory for graphs — a survey, (), 52-75
[23] Burr, S.A., Diagonal Ramsey numbers for small graphs, J. graph theory, 7, 57-69, (1983) · Zbl 0513.05041
[24] Caro, Y., On zero-sum Ramsey numbers — matchings, Techn. report univ. of Haifa, ORANIM, (1990)
[25] Caro, Y., On zero-sum delta systems and multiple copies of hypergraphs, J. graph theory, 15, 511-521, (1991) · Zbl 0762.05081
[26] Caro, Y., On zero-sum Ramsey numbers — stars, Discrete math., 104, 1-6, (1992) · Zbl 0771.05068
[27] Caro, Y., On q-divisible hypergraphs, Ars combin., 33, 321-328, (1992) · Zbl 0777.05083
[28] Caro, Y., On several variations of the turan and Ramsey numbers, J. graph theory, 16, 257-266, (1992) · Zbl 0760.05066
[29] Caro, Y., On zero-sum turan numbers — stars and cycles, Ars combin., 33, 193-198, (1992) · Zbl 0771.05054
[30] Cano, Y., On zero-sum Ramsey numbers — complete graphs, Quart. J. math. Oxford, 43, 2, 175-181, (1992) · Zbl 0771.05069
[31] Caro, Y., Zero-sum bipartite Ramsey numbers, Czechoslovak math. J., 43, 107-114, (1993) · Zbl 0788.05070
[32] Y. Caro, Miscellaneous zero-sum problems, preprint.
[33] Caro, Y., On induced subgraphs with odd degrees, Discrete math., 132, 23-28, (1994) · Zbl 0808.05090
[34] Caro, Y., A complete characterization of the zero-sum (mod 2) Ramsey numbers, J. combin. theory ser. A, 68, 205-211, (1994) · Zbl 0808.05075
[35] Caro, Y., Exact cuts and a simple proof of the zero graphs theorem, Ars combin., 41, (1995) · Zbl 0856.05069
[36] Caro, Y., A linear upper bound in zero-sum Ramsey theory, Internat. J. of math., 17, 609-612, (1994) · Zbl 0805.05056
[37] Y. Caro, Problems in zero-sum combinatorics, J. London Math. Soc., to appear. · Zbl 0883.05102
[38] Caro, Y.; Krasikov, I.; Roditty, Y., On induced subgraphs of trees, with restricted degrees, Discrete math., 125, 101-106, (1994) · Zbl 0796.05028
[39] Caro, Y.; Roditty, Y., On zero-sum turan numbers problems of bialostocki and dierker, Australian math. soc. ser. A, 53, 402-407, (1992) · Zbl 0759.05062
[40] Caro, Y.; Roditty, Y., A zero-sum conjecture for trees, Ars combin., 40, 89-96, (1995) · Zbl 0836.05057
[41] Caro, Y.; Tuza, Zs., On local and Mean k-colorings of graphs and hypergraphs, Quart. J. math., 44, 385-398, (1993) · Zbl 0786.05034
[42] Chung, F.R.K.; Graham, R.L., Edge-colored complete graphs with precisely colored subgraphs, Combinatorica, 3, 315-324, (1983) · Zbl 0529.05041
[43] Danilov, A.N., The Cauchy-Davenport-chowla theorem for groups, (), 50-59, (in Russian) · Zbl 0493.10052
[44] Davenport, H., On the addition of residue classes, J. London math. soc., 10, 30-32, (1935) · Zbl 0010.38905
[45] Erdo˝s, P.; Ginzburg, A.; Ziv, A., Theorem in additive number theory, Bull. res. council Israel 10F, 41-43, (1961)
[46] Erdo˝s, P.; Graham, R.L., Old and new results in combinatorial number theory, (), Geneva · Zbl 0434.10001
[47] Erdo˝s, P.; Szekeres, G., A combinatorial problem in geometry, Compos. math., 2, 463-470, (1935) · JFM 61.0651.04
[48] C. Flores and O. Ordaz, On sequences with zero-sum in Abelian groups, Discrete Math., to appear. · Zbl 0874.11028
[49] Frankl, P., The shifting technique in extremal set theory, London math. soc. lect. note ser. 123, 81-110, (1987)
[50] Furedi, Z., Turan type problems, Rutcor research report 2-91, (February, 1991)
[51] Furedi, Z.; Kleitman, D., On zero-trees, J. graph. theory, 16, 107-120, (1992) · Zbl 0772.05033
[52] Furedi, Z.; Kleitman, D., The minimum number of zero-sets, Combinatorics, paul erdo˝s is eighty, Vol. 1, (1993) · Zbl 0795.05014
[53] Gyarfas, J.; Lehel, J.; Nesetril, J.; Rodl, V.; Schelp, R.; Tuza, Zs., Local k-colorings of graphs and hypergraphs, J. combin. theory ser. B, 43, 127-139, (1987) · Zbl 0632.05041
[54] Gyarfas, J.; Lehel, J.; Schelp, R.; Tuza, Zs., Ramsey numbers for local colorings, Graphs combin., 3, 267-277, (1987) · Zbl 0621.05023
[55] Graham, R.L.; Rodl, V., Numbers in Ramsey theory, London math. soc. lecture notes ser., 123, 111-153, (1987)
[56] Graham, R.L.; Rothschild, B.; Spencer, J., Ramsey theory, (1990), Wiley New York · Zbl 0705.05061
[57] Hamidoune, Y., A note on the addition of residues, Graphs and combin., 6, 147-152, (1990) · Zbl 0745.11009
[58] Hamidoune, Y., On the subsets product in finite groups, Europ. J. combin., 12, 211-221, (1991) · Zbl 0736.20013
[59] Y. Hamidoune, private communication, 1993.
[60] Harary, F.; Harborth, H.; Mengersen, I., Generalized Ramsey theory for graphs XII: bipartite Ramsey sets, Glasgow math. J., 22, 31-41, (1981) · Zbl 0478.05065
[61] Harborth, H., Ein extremalproblem fur gitterpunkte, J. reine angew. math., 262/263, 356-360, (1973) · Zbl 0268.05008
[62] M. Kisin, The number of zero-sums modulo m in a sequence of length n, submitted. · Zbl 0804.11019
[63] Kneser, M., Abschatzaugen der asymptotischen dichte von summenmengen, Math. Z, 58, 459-484, (1953) · Zbl 0051.28104
[64] Lovasz, L., Combinatorial problems and exercises, (1979), North-Holland Amsterdam · Zbl 0439.05001
[65] Mader, W., Homomorphiesatze fur graphen, Math. ann., 178, 154-168, (1968) · Zbl 0165.57401
[66] Olson, J.E., On a combinatorial problem of erdo˝s-Ginzburg-Ziv, J. number theory, 8, 52-57, (1976) · Zbl 0333.05009
[67] Roditty, Y., On zero-sum Ramsey-numbers of multiple copies of a graph, Ars combin., 35A, 89-95, (1993) · Zbl 0840.05060
[68] Schrijver, L.; Seymour, P.D., Spanning trees of different weights, (), 281-288 · Zbl 0734.05032
[69] Schrijver, L.; Seymour, P.D., A simpler proof of the zero-trees theorem, J. combin. theory, set. A, 58, 301-305, (1991) · Zbl 0756.05085
[70] Simonovits, M., Extremal graph theory, (), 161-200 · Zbl 0531.05037
[71] Simonovits, M., Extremal graph problems, degenerate extremal problems and supersaturated graphs, (), 419-437
[72] Truszczynski, M.; Tuza, Zs., Linear upper bounds for local Ramsey numbers, Graphs combin., 3, 67-73, (1987) · Zbl 0612.05045
[73] P. Van Emde Boas and D. Kruyswijk, A combinatorial problem on finite abelian groups III, Z.W. (1969-008) Math. Centrum-Amsterdam. · Zbl 0245.20046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.