Abstract
We present several variants of the sunflower conjecture of Erdős & Rado (J Lond Math Soc 35:85–90, 1960) and discuss the relations among them.
We then show that two of these conjectures (if true) imply negative answers to the questions of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990) and Cohn et al. (2005) regarding possible approaches for obtaining fast matrix-multiplication algorithms. Specifically, we show that the Erdős–Rado sunflower conjecture (if true) implies a negative answer to the “no three disjoint equivoluminous subsets” question of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990); we also formulate a “multicolored” sunflower conjecture in \({\mathbb{Z}_3^n}\) and show that (if true) it implies a negative answer to the “strong USP” conjecture of Cohn et al. (2005) (although it does not seem to impact a second conjecture in Cohn et al. (2005) or the viability of the general group-theoretic approach). A surprising consequence of our results is that the Coppersmith–Winograd conjecture actually implies the Cohn et al. conjecture.
The multicolored sunflower conjecture in \({\mathbb{Z}_3^n}\) is a strengthening of the well-known (ordinary) sunflower conjecture in \({\mathbb{Z}_3^n}\) , and we show via our connection that a construction from Cohn et al. (2005) yields a lower bound of (2.51 . . .)n on the size of the largest multicolored 3-sunflower-free set, which beats the current best-known lower bound of (2.21 . . . )n Edel (2004) on the size of the largest 3-sunflower-free set in \({\mathbb{Z}_3^n}\) .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon N., Boppana R.B (1987) The monotone circuit complexity of Boolean functions. Combinatorica 7(1): 1–22
Zs. Baranyai (1975). On the factorization of the complete uniform hypergraph. In Infinite and finite sets, Proc. Coll. Keszthely, 1973, (A. Hajnal, R. Rado and V.T. Sós, eds.), Colloquia Math. Soc. János Bolyai 10. North-Holland.
Bateman M., Katz N.H (2012) New bounds on cap sets. J. of the AMS 25(2): 585–613
P. Bürgisser, M. Clausen & M. A. Shokrollahi (1997). Algebraic Complexity Theory. Springer.
H. Cohn, R. D. Kleinberg, B. Szegedy & C. Umans (2005). Group-theoretic Algorithms for Matrix Multiplication. In Proceedings of the 46th Annual FOCS, 379–388.
H. Cohn & C. Umans (2003). A Group-theoretic Approach to Fast Matrix Multiplication. In Proceedings of the 44th Annual FOCS, 438–449.
D. Coppersmith & S. Winograd (1990). Matrix multiplication via arithmetic progression. J. of Symbolic Computation 9, 251–280.
W. A. Deuber, P. Erdös, D. S. Gunderson, A. V. Kostochka & A. G. Meyer (1997). Intersection Statements for Systems of Sets. J. Comb. Theory, Ser. A 79(1), 118–132.
Y. Edel (2004). Extensions of generalized product caps 31(1), 5–14.
P. Erdős (1971). Some unsolved problems in graph theory and com binatorial analysis. In Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), 97–109. Academic Press, London.
P. Erdős (1975). Problems and results on finite and infinite combi natorial analysis. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday) Vol. I; Colloq. Math. Soc., János Bolyai, editor, volume 10, 403–424. North-Holland, Amster717 dam.
P. Erdős (1981). On the combinatorial problems which I would most like to see solved. Combinatorica 1(1), 25–42.
P. Erdős & R. Rado (1960). Intersection theorems for systems of sets. J. London Math. Soc. 35, 85–90.
P. Erdős & R. Rado (1969). Intersection theorems for systems of sets II. J. London Math. Soc. 44, 467–479.
P. Erdős & E. Szemerédi (1978). Combinatorial properties of sys tems of sets. J. Combinatorial Theory Ser. A 24(3), 308–313.
Z. Füredi (1991). Turán type problems. Surveys in combinatorics, London Math. Soc. Lecture Note Ser. 166, 253–300. Cambridge Univ. Press.
J. von zur Gathen (1988). Algebraic Complexity Theory. Annual review of computer science 3, 317–347.
S. Jukna (2001). Extremal Combinatorics. Springer.
A. V. Kostochka (1997). A bound of the cardinality of families not containing Δ-systems. In The mathematics of Paul Erdős, II, Algo rithms Combin., volume 14, 229–235. Springer.
R. Meshulam (1995). On Subsets of Finite Abelian Groups with No 3-Term Arithmetic Progressions. J. Comb. Theory, Ser. A 71(1), 168–172.
A. A. Razborov (1985). Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk. SSSR 281(4), 798–801. In Russian.
R. Salem & D. Spencer (1942). On sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci. (USA) 28, 561.
J. Spencer (1977). Intersection Theorems for Systems of Sets. Canadian Math Bulletin 20(2), 249–254.
A. Stothers (2010). On the complexity of matrix multiplication. Ph.D. thesis, U. Edinburgh.
Strassen V (1969) Gaussian elimination is not optimal. Numer. Math 13: 354–356
V. Strassen (1987). Relative bilinear complexity and matrix multi plication.J. Reine Angew. Math. 375/376, 406–443.
V. Vassilevska Williams (2012). Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th annual STOC, 887–898.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Alon, N., Shpilka, A. & Umans, C. On sunflowers and matrix multiplication. comput. complex. 22, 219–243 (2013). https://doi.org/10.1007/s00037-013-0060-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-013-0060-1