×

Uniform hypergraphs containing no grids. (English) Zbl 1278.05161

Summary: A hypergraph is called an \(r \times r\) grid if it is isomorphic to a pattern of \(r\) horizontal and \(r\) vertical lines, i.e., a family of sets \(\{A_1, \dots, A_r, B_1, \dots, B_r\}\) such that \(A_i\cap A_j=B_i\cap B_j=\emptyset \) for \(1\leq i<j\leq r\) and \(|A_i\cap B_j|=1\) for \(1\leq i,j\leq r\). Three sets \(C_1,C_2,C_3\) form a triangle if they pairwise intersect in three distinct singletons, \(|C_1\cap C_2|=|C_2\cap C_3|=|C_3\cap C_1|=1\), \(C_1\cap C_2\neq C_1\cap C_3\). A hypergraph is linear, if \(|E\cap F|\leq 1\) holds for every pair of edges \(E\neq F\). In this paper we construct large linear \(r\)-hypergraphs which contain no grids. Moreover, a similar construction gives large linear \(r\)-hypergraphs which contain neither grids nor triangles. For \(r\geq 4\) our constructions are almost optimal. These investigations are motivated by coding theory: we get new bounds for optimal superimposed codes and designs.

MSC:

05C65 Hypergraphs
05C42 Density (toughness, etc.)
05D05 Extremal set theory
11B25 Arithmetic progressions
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N.; Asodi, V., Tracing a single user, European J. Combin., 27, 1227-1234 (2006) · Zbl 1105.05068
[2] Alon, N.; Asodi, V., Tracing many users with almost no rate penalty, IEEE Trans. Inform. Theory, 53, 437-439 (2007) · Zbl 1310.94230
[3] Alon, N.; Shapira, A., On an extremal hypergraph problem of Brown, Erdős and Sós, Combinatorica, 26, 627-645 (2006) · Zbl 1121.05079
[4] Babai, L.; Sós, V. T., Sidon sets in groups and induced subgroups of Cayley graphs, European J. Combin., 6, 101-114 (1985) · Zbl 0573.05032
[5] Baranyai, Zs., On the factorization of the complete uniform hypergraph, (Infinite and Finite Sets, Keszthely, Hungary, 1973. Vol. I. Infinite and Finite Sets, Keszthely, Hungary, 1973. Vol. I, Proc. Colloq. Math. Soc. János Bolyai, vol. 10 (1975), North-Holland: North-Holland Amsterdam), 91-108 · Zbl 0306.05137
[6] Behrend, F. A., On sets of integers which contain no three terms in arihtmetical progression, Proc. Nat. Acad. Sci. USA, 32, 331-332 (1946) · Zbl 0060.10302
[9] Brown, W. G., On graphs that do not contain a Thomsen graph, Canad. Math. Bull., 9, 281-289 (1966) · Zbl 0178.27302
[10] Brown, W. G.; Erdős, P.; Sós, V. T., On the existence of triangulated spheres in 3-graphs and related problems, Period. Math. Hungar., 3, 221-228 (1973) · Zbl 0269.05111
[11] Brown, W. G.; Erdős, P.; Sós, V. T., Some extremal problems on \(r\)-graphs, (Proceedings of the Third Annual Arbor Conference on Graph Theory. Proceedings of the Third Annual Arbor Conference on Graph Theory, New Directions in the Theory of the Graphs (1973), Academic Press: Academic Press New York), 55-63
[12] Caro, Y.; Yuster, R., Packing graphs: the packing problem solved, Electron. J. Combin., 4, 7 (1997), Research Paper 1 · Zbl 0885.05052
[13] Colbourn, C. J.; Mendelsohn, E.; Rosa, A.; Širáň, J., Anti-mitre Steiner triple systems, Graphs Combin., 10, 215-224 (1994) · Zbl 0815.05017
[14] Colbourn, C. J.; Rosa, A., Triple Systems (1999), Clarendon Press, Oxford University Press: Clarendon Press, Oxford University Press New York · Zbl 0938.05009
[16] De Bonis, A.; Vaccaro, U., Optimal algorithms for two group testing problems and new bounds on generalized superimposed codes, IEEE Trans. Inform. Theory, 52, 4673-4680 (2006) · Zbl 1320.94056
[17] D’yachkov, A. G.; Rykov, V. V., Bounds on the length of disjunctive codes, Problemy Peredaci Informacii, 18, 7-13 (1982) · Zbl 0507.94013
[18] D’yachkov, A. G.; Rykov, V. V., Optimal superimposed codes and designs for Rényi’s search model, J. Statist. Plann. Inference, 100, 281-302 (2002) · Zbl 0998.94043
[19] Erdős, P., Extremal problems in graph theory, (Fiedler, M., Theory of Graphs and its Applications (1964), Academic Press: Academic Press New York), 29-36
[20] Erdős, P., On extremal problems of graphs and generalized graphs, Israel J. Math., 2, 183-190 (1964) · Zbl 0129.39905
[21] Erdős, P., Problems and results in combinatorial analysis, (Colloq. Internazionale Teorie Combinatorie (Rome, 1973), Tomo II. Colloq. Internazionale Teorie Combinatorie (Rome, 1973), Tomo II, Atti dei Convegni Lincei, vol. 17 (1976), Accad. Naz. Lincei: Accad. Naz. Lincei Rome), 3-17
[22] Erdős, P.; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of two others, J. Combin. Theory Ser. A, 33, 158-166 (1982) · Zbl 0489.05003
[23] Erdős, P.; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of \(r\) others, Israel J. Math., 51, 79-89 (1985) · Zbl 0587.05021
[24] Erdős, P.; Frankl, P.; Rödl, V., The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin., 2, 113-121 (1986) · Zbl 0593.05038
[25] Erdős, P.; Rényi, A.; Sós, V. T., On a problem of graph theory, Studia Sci. Math. Hungar., 1, 215-235 (1966) · Zbl 0144.23302
[26] Erdős, P.; Simonovits, M., Compactness results in extremal graph theory, Combinatorica, 2, 275-288 (1982) · Zbl 0508.05043
[27] Erdős, P.; Turán, P., On a problem of Sidon in additive number theory and some related problems, J. Lond. Math. Soc., 16, 212-215 (1941) · JFM 67.0984.03
[28] Ericson, T.; Györfi, L., Superimposed codes in \(R^n\), IEEE Trans. Inform. Theory, 34, 877-880 (1988) · Zbl 0657.94014
[29] Forbes, A. D.; Grannell, M. J.; Griggs, T. S., On 6-sparse Steiner triple systems, J. Combin. Theory Ser. A, 144, 235-252 (2007) · Zbl 1121.05015
[30] Forbes, A. D.; Grannell, M. J.; Griggs, T. S., Further 6-sparse Steiner triple systems, Graphs Combin., 25, 49-64 (2009) · Zbl 1188.05034
[31] Frankl, P.; Füredi, Z., A new extremal property of Steiner triple systems, Discrete Math., 48, 205-212 (1984) · Zbl 0553.05019
[32] Frankl, P.; Füredi, Z., Union-free families of sets and equations over fields, J. Number Theory, 23, 210-218 (1986) · Zbl 0589.05013
[33] Frankl, P.; Füredi, Z., Exact solution of some Turán-type problems, J. Combin. Theory, Ser. A, 45, 226-262 (1987) · Zbl 0661.05003
[34] Fujiwara, Y., Infinite classes of anti-mitre and 5-sparse Steiner triple systems, J. Combin. Des., 14, 237-250 (2006) · Zbl 1089.05012
[35] Füredi, Z., A note on \(r\)-cover-free families, J. Combin. Theory Ser. A, 73, 172-173 (1996) · Zbl 0843.05100
[37] Füredi, Z.; Ruszinkó, M., An improved upper bound of the rate of Euclidean superimposed codes, IEEE Trans. Inform. Theory, 45, 799-802 (1999) · Zbl 0945.94031
[38] Grannell, M. J.; Griggs, T. S.; Whitehead, C. A., The resolution of the anti-Pasch conjecture, J. Combin. Des., 8, 300-309 (2000) · Zbl 0959.05016
[39] Griggs, T. S.; Murphy, J. P., 101 anti-Pasch Steiner triple systems of order 19, J. Combin. Math. Combin. Comput., 13, 129-141 (1993) · Zbl 0778.05022
[40] Griggs, T. S.; Murphy, J.; Phelan, J. S., Anti-Pasch Steiner triple systems, J. Combin. Inf. Syst. Sci., 15, 79-84 (1990) · Zbl 0741.05009
[41] Heath-Brown, D. R., Integer sets containing no arithmetic progression, J. Lond. Math. Soc., 35, 385-394 (1987) · Zbl 0589.10062
[42] Hwang, F. K., A method for detecting all defective members in a population by group testing, J. Amer. Statist. Assoc., 67, 339, 605-608 (1972) · Zbl 0247.62010
[43] Hwang, F. K.; Sós, V. T., Non adaptive hypergeometric group testing, Studia Sci. Math. Hungar., 22, 257-263 (1987) · Zbl 0639.62076
[44] Iwaniec, H.; Pintz, J., Primes in short intervals, Monatsh. Math., 98, 115-143 (1984) · Zbl 0544.10040
[45] Johnson, S. M., On the upper bounds for unrestricted binary error-correcting codes, IEEE Trans. Inform. Theory, 17, 466-478 (1971) · Zbl 0231.94008
[46] Johnson, S. M., A new upper bound for error-correcting codes, IRE Trans. Inform. Theory, 8, 203-207 (1962) · Zbl 0102.34602
[47] Johnson, S. M., Improved asymptotic bounds for error-correcting codes, IEEE Trans. Inform. Theory, 9, 198-205 (1963) · Zbl 0282.94010
[48] Kautz, W. H.; Singleton, R. C., Nonrandom binary superimposed codes, IEEE Trans. Inform. Theory, 10, 363-377 (1964) · Zbl 0133.12402
[49] Kim, H. K.; Lebedev, V., On optimal superimposed codes, J. Combin. Des., 12, 79-91 (2004) · Zbl 1051.94013
[50] Kim, H. K.; Lebedev, V.; Oh, D. Y., Some new results on superimposed codes, J. Combin. Des., 13, 276-285 (2005) · Zbl 1169.94350
[51] Ling, A. C.H., A direct product construction for 5-sparse triple systems, J. Combin. Des., 5, 443-447 (1997) · Zbl 0912.05012
[52] Ling, A. C.H.; Colbourn, C. J.; Grannell, M. J.; Griggs, T. S., Construction techniques for anti-Pasch Steiner triple systems, J. Lond. Math. Soc. (2), 61, 641-657 (2000) · Zbl 0956.05023
[53] Macula, A. J., A simple construction of \(d\)-disjunct matrices with certain constant weights, Discrete Math., 162, 311-312 (1996) · Zbl 0870.05012
[55] Nguyen Quang, A.; Zeisel, T., Bounds on constant weight binary superimposed codes, Probl. Control Inf. Theory, 17, 223-230 (1988) · Zbl 0652.94021
[56] Ray-Chaudhuri, D. K.; Wilson, R. M., The existence of resolvable block designs, (Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), North-Holland: North-Holland Amsterdam), 361-375
[57] Ruszinkó, M., On the upper bound of the size of the \(r\)-cover-free families, J. Combin. Theory Ser. A, 66, 302-310 (1994) · Zbl 0798.05071
[58] Ruzsa, I. Z., Solving a linear equation in a set of integers I, Acta Arith., 65, 259-282 (1993) · Zbl 1042.11525
[60] Sárközy, G. N.; Selkow, S., An extension of the Ruzsa-Szemerédi theorem, Combinatorica, 25, 77-84 (2005) · Zbl 1065.05068
[61] Sárközy, G. N.; Selkow, S., On a Turán-type hypergraph problem of Brown, Erdős and T. Sós, Discrete Math., 297, 190-195 (2005) · Zbl 1079.05063
[62] Shapira, A., Behrend-type constructions for sets of linear equations, Acta Arith., 122, 17-33 (2006) · Zbl 1149.11012
[63] Sós, V. T., An additive problem in different structures, (Proc. of the Second Int. Conf. in Graph Theory, Combinatorics, Algorithms, and Applications. Proc. of the Second Int. Conf. in Graph Theory, Combinatorics, Algorithms, and Applications, San Fra. Univ., California, July 1989 (1991), SIAM: SIAM Philadelphia), 486-510 · Zbl 0760.05088
[64] Szemerédi, E., On sets of integers containing no \(k\) elements in arithmetic progression, Acta Arith., 27, 199-245 (1975) · Zbl 0303.10056
[65] Szemerédi, E., Integer sets containing no arithmetic progression, Acta Math. Hungar., 56, 155-158 (1990) · Zbl 0721.11007
[67] Wilson, R. M., On existence theory for pairwise balanced designs, I, II, III, J. Combin. Theory Ser. A, 13, 220-245 (1972), 246-273, 18 (1975), 71-79 · Zbl 0263.05014
[68] Wolfe, A., 5-sparse Steiner triple systems of order \(n\) exist for almost all admissible \(n\), Electron. J. Combin., 12, 42 (2005), Research Paper 68 · Zbl 1079.05013
[69] Wolfe, A., The resolution of the anti-mitre Steiner triple system conjecture, J. Combin. Des., 14, 229-236 (2006) · Zbl 1089.05013
[70] Wolfe, A. J., The existence of 5-sparse Steiner triple systems of order \(n \equiv 3 \sim(\operatorname{mod} 6), n \notin \{9, 15 \} \), J. Combin. Theory Ser. A, 115, 1487-1503 (2008) · Zbl 1157.05011
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.