Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-07T04:02:53.712Z Has data issue: false hasContentIssue false
  • English
  • Français

2-Cancellative Hypergraphs and Codes

Published online by Cambridge University Press:  02 February 2012

ZOLTÁN FÜREDI
ZOLTÁN FÜREDI*
Affiliation:
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA and Rényi Institute of Mathematics of the Hungarian Academy of Sciences, Budapest, PO Box 127, Hungary-1364 (e-mail: z-furedi@illinois.edu, furedi@renyi.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A family of sets (and the corresponding family of 0–1 vectors) is called t-cancellative if, for all distinct t + 2 members A1,. . ., At and B, C ∈ , A_1\cup\cdots \cup A_t\cup B \neq A_1\cup \cdots \cup A_t \cup C. \] Let ct(n) be the size of the largest t-cancellative family on n elements, and let ct(n, r) denote the largest r-uniform family. We improve the previous upper bounds, e.g., we show c2(n) ≤ 20.322n (for n > n0). Using an algebraic construction we show that c2(n, 2k) = Θ(nk) for each k when n → ∞.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 159 - 177
Copyright
Copyright © Cambridge University Press 2012

References

[1]Alon, N. and Asodi, V. (2006) Tracing a single user. European J. Combin. 27 1227–1234.CrossRefGoogle Scholar
[2]Alon, N., Fachini, E. and Körner, J. (2000) Locally thin set families. Combin. Probab. Comput. 9 481–488.CrossRefGoogle Scholar
[3]Alon, N., Körner, J. and Monti, A. (2000) String quartets in binary. Combin. Probab. Comput. 9 381–390.CrossRefGoogle Scholar
[4]Alon, N. and Shapira, A. (2006) On an extremal hypergraph problem of Brown, Erdős and Sós. Combinatorica 26 627–645.CrossRefGoogle Scholar
[5]Bollobás, B. (1974) Three-graphs without two triples whose symmetric difference is contained in a third. Discrete Math. 8 21–24.CrossRefGoogle Scholar
[6]Brown, W. G., Erdős, P. and Sós, V. T. (1973) Some extremal problems on r-graphs. In New Directions in the Theory of Graphs: Proc. Third Ann Arbor Conference, 1971, Academic Press, 53–63.Google Scholar
[7]Brown, W. G., Erdős, P. and Sós, V. T. (1973) On the existence of triangulated spheres in 3-graphs, and related problems. Period. Math. Hungar. 3 221–228.Google Scholar
[8]Coppersmith, D. and Shearer, J. B. (1998) New bounds for union-free families of sets. Electron. J. Combin. 5 #39.CrossRefGoogle Scholar
[9]De Bonis, A. and Vaccaro, U., (2006) Optimal algorithms for two group testing problems and new bounds on generalized superimposed codes. IEEE Trans. Inform. Theory 52 4673–4680.CrossRefGoogle Scholar
[10]D'yachkov, A. G. and Rykov, V. V. (1982) Bounds on the length of disjunctive codes. Problemy Peredaci Informacii 18 7–13.Google Scholar
[11]Erdős, P. (1964) Extremal problems in graph theory. In Theory of Graphs and its Applications (Fiedler, M., ed.), Academic Press, pp. 29–36.Google Scholar
[12]Erdős, P., Frankl, P. and Füredi, Z. (1982) Families of finite sets in which no set is covered by the union of two others. J. Combin. Theory Ser. A 33 158–166.Google Scholar
[13]Erdős, P., Frankl, P. and Füredi, Z. (1985) Families of finite sets in which no set is covered by the union of r others. Israel J. Math. 51 79–89.CrossRefGoogle Scholar
[14]Erdős, P., Frankl, P. and Rödl, V. (1986) The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. 2 113–121.CrossRefGoogle Scholar
[15]Erdős, P. and Kleitman, D. J. (1968) On coloring graphs to maximize the proportion of multicolored k-edges. J. Combin. Theory 5 164–169.Google Scholar
[16]Erdős, P. and Szemerédi, E. (1978) Combinatorial properties of systems of sets. J. Combin. Theory Ser. A 24 308–313.Google Scholar
[17]Fachini, E., and Körner, J. and Monti, A. (2001) A better bound for locally thin set families. J. Combin. Theory Ser. A 95 209–218.CrossRefGoogle Scholar
[18]Frankl, P. (1990) Asymptotic solution of a Turán-type problem. Graphs Combin. 6 223–227.Google Scholar
[19]Frankl, P. and Füredi, Z. (1984) Union-free hypergraphs and probability theory. European J. Combin. 5 (1984), 127–131. Erratum, ibid. 5 395.Google Scholar
[20]Frankl, P. and Füredi, Z. (1987) Colored packing of sets. In Combinatorial Design Theory, Ann. Discrete Math. 34 165–178.CrossRefGoogle Scholar
[21]Frankl, P. and Füredi, Z. (1989) Extremal problems whose solutions are the blow-ups of the small Witt-designs. J. Combin. Theory Ser. A 52 129–147.Google Scholar
[22]Füredi, Z. (1996) On r-cover-free families. J. Combin. Theory Ser. A 73 172–173.CrossRefGoogle Scholar
[23]Füredi, Z. and Ruszinkó, M. (2011) Uniform hypergraphs containing no grids. Manuscript arXiv:1103.1691 [math.CO]Google Scholar
[24]Hwang, F. K. and Sós, V. T. (1987) Non adaptive hypergeometric group testing. Studia Sci. Math. Hungar. 22 257–263.Google Scholar
[25]Johnson, S. M. (1971) On the upper bounds for unrestricted binary error-correcting codes. IEEE Trans. Inform. Theory 17 466–478.CrossRefGoogle Scholar
[26]Katona, G. O. H. (1974) Extremal problems for hypergraphs. In Combinatorics: Proc. NATO Advanced Study Inst., Breukelen 1974, Part 2, Graph Theory: Foundations, Partitions and Combinatorial Geometry, Vol. 56 of Math. Centre Tracts, Math. Centrum, pp. 13–42.Google Scholar
[27]Kautz, W. H. and Singleton, R. C. (1964) Nonrandom binary superimposed codes. IEEE Trans. Inform. Theory 10 363–377.Google Scholar
[28]Keevash, P. and Mubayi, D. (2004) Stability theorems for cancellative hypergraphs. J. Combin. Theory Ser. B 92 163–175.Google Scholar
[29]Keevash, P. and Sudakov, B. (2005) On a hypergraph Turán problem of Frankl. Combinatorica 25 673–706.Google Scholar
[30]Körner, J. (1995) On the extremal combinatorics of the Hamming space. J. Combin. Theory Ser. A 71 112–126.Google Scholar
[31]Körner, J. and Monti, A. (2002) Delta-systems and qualitative (in)dependence. J. Combin. Theory Ser. A 99 75–84.CrossRefGoogle Scholar
[32]Körner, J. and Sinaimeri, B. (2007) On cancellative set families. Combin. Probab. Comput. 16 767–773.CrossRefGoogle Scholar
[33]Lidl, R. and Niederreiter, H. (1994) Introduction to Finite Fields and their Applications, Cambridge University Press.Google Scholar
[34]Nguyen Quang, A, and Zeisel, T. (1988) Bounds on constant weight binary superimposed codes. Probl. Control Inform. Theory 17 223–230.Google Scholar
[35]Pikhurko, O. (2008) An exact Turán result for the generalized triangle. Combinatorica 28 187–208.Google Scholar
[36]Ruszinkó, M. (1994) On the upper bound of the size of the r-cover-free families. J. Combin. Theory Ser. A 66 302–310.CrossRefGoogle Scholar
[37]Ruzsa, I. Z. and Szemerédi, E. (1978) Triple systems with no six points carrying three triangles. In Combinatorics, Vol. II: Proc. Fifth Hungarian Colloq., Keszthely 1976, Vol. 18 of Colloq. Math. Soc. János Bolyai, North-Holland, pp. 939–945.Google Scholar
[38]Sárközy, G. N. and Selkow, S. (2005) An extension of the Ruzsa–Szemerédi theorem. Combinatorica 25 77–84.Google Scholar
[39]Sárközy, G. N. and Selkow, S. (2005) On a Turán-type hypergraph problem of Brown, Erdős and T. Sós. Discrete Math. 297 190–195.CrossRefGoogle Scholar
[40]Shearer, J. B. (1996) A new construction for cancellative families of sets. Electron. J. Combin. 3 #15.CrossRefGoogle Scholar
[41]Sidorenko, A. F. (1987) The maximal number of edges in a homogeneous hypergraph containing no prohibited subgraphs. Math. Notes 41 247–259. Translated from Mat. Zametki.Google Scholar
[42]Sidorenko, A. F. (1989) Extremal combinatorial problems in spaces with continuous measure (in Russian). Issledovanie Operatchiy i ASU 34 34–40.Google Scholar
[43]Sidorenko, A. (1992) Asymptotic solution of the Turán problem for some hypergraphs. Graphs Combin. 8 199–201.CrossRefGoogle Scholar
[44]Sós, V. T. (1991) An additive problem in different structures. Combinatorics, Algorithms, and Applications: Proc. Second International Conference in Graph Theory, San Francisco 1989, SIAM, pp. 486–510.Google Scholar
[45]Tolhuizen, L. (2000) New rate pairs in the zero-error capacity region of the binary multiplying channel without feedback. IEEE Trans. Inform. Theory 46 1043–1046.CrossRefGoogle Scholar