Year 2020, Volume 7 , Issue 2, Pages 161 - 181 2020-05-07

Some bounds arising from a polynomial ideal associated to any $t$-design

William J. MARTIN [1] , Douglas R. STINSON [2]


We consider ordered pairs $(X,\mathcal{B})$ where $X$ is a finite set of size $v$ and $\mathcal{B}$ is some collection of $k$-element subsets of $X$ such that every $t$-element subset of $X$ is contained in exactly $\lambda$ ``blocks'' $B\in \mathcal{B}$ for some fixed $\lambda$. We represent each block $B$ by a zero-one vector $\bc_B$ of length $v$ and explore the ideal $\mathcal{I}(\mathcal{B})$ of polynomials in $v$ variables with complex coefficients which vanish on the set $\{ \bc_B \mid B \in \mathcal{B}\}$. After setting up the basic theory, we investigate two parameters related to this ideal: $\gamma_1(\mathcal{B})$ is the smallest degree of a non-trivial polynomial in the ideal $\mathcal{I}(\mathcal{B})$ and $\gamma_2(\mathcal{B})$ is the smallest integer $s$ such that $\mathcal{I}(\mathcal{B})$ is generated by a set of polynomials of degree at most $s$. We first prove the general bounds $t/2 < \gamma_1(\mathcal{B}) \le \gamma_2(\mathcal{B}) \le k$. Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have $\gamma_2(\mathcal{B}) \le t$. But we expect $\gamma_2(\mathcal{B})$ to be closer to $k$ for less structured designs and we indicate this by constructing infinitely many triple systems satisfying $\gamma_2(\mathcal{B})=k$.
Design, Steiner system, Polynomial ideal, Bounds
  • [1] A. E. Brouwer, The Witt designs, Golay codes and Mathieu groups, Unpublished notes, https: //www.win.tue.nl/~aeb/2WF02/Witt.pdf.
  • [2] D. Bryant, D. Horsley, A proof of Lindner’s conjecture on embeddings of partial Steiner triple systems. J. Combin. Des. 17 (2009) 63–89.
  • [3] A. R. Calderbank, P. Delsarte, Extending the t–design concept, Trans. Amer. Math. Soc. 338 (1993) 941–952.
  • [4] P. J. Cameron, Near–regularity conditions for designs, Geom. Dedicata 2 (1973) 213–223.
  • [5] M. Conder, C. D. Godsil, The symmetric group as a polynomial space, Combinatorial and Graph- Theoretical Problems in Linear Algebra (R.A. Brualdi, S. Friedland and V. Klee, eds.) IMA Vol. Math. Appl. 50 (1993) 219–227.
  • [6] D. Cox, J. Little, D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (4th ed.), Springer-Verlag Undergraduate Texts in Mathematics, Springer-Verlag, New York, 2015.
  • [7] E. Croot, V. F. Lev, P. P. Pach, Progression–free sets in $\\mathbb{Z}_4^n$ are exponentially small, Ann. of Math. 185 (2017) 331–337.
  • [8] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Reports Suppl. No. 10, 1973.
  • [9] P. Delsarte, Hahn polynomials, discrete harmonics, and t-designs, SIAM J. Appl. Math. 34(1) (1978) 157–166.
  • [10] D. S. Dummit, R. M. Foote, Abstract Algebra (3rd ed.), John Wiley and Sons, Hoboken, 2004.
  • [11] J. S. Ellenberg, D. Gijswijt, On large subsets of $F_q^n$ with no three-term arithmetic progression, Ann. of Math. 185 (2017) 339–343.
  • [12] A. D. Forbes, M. J. Grannell, T. S. Griggs, Configurations and trades in Steiner triple systems, Australas. J. Combin. 29 (2004) 75–84.
  • [13] W. Fulton, Algebraic Curves: An Introduction to Algebraic Geometry, Advanced Book Classics, Addison-Wesley, Reading, Mass., 1989.
  • [14] C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
  • [15] G.-M. Greuel, G. Pfister, H. Schönemann, Singular 3.0.2. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern, 2005.
  • [16] P. Keevash, The existence of designs, Preprint v.3, (2019) arXiv:1401.3665.
  • [17] W. J. Martin, C. L. Steele, On the ideal of the shortest vectors in the Leech lattice and other lattices, J. Algebraic Combin. 41(3) (2015) 707–726.
  • [18] W. J. Martin, An ideal associated to any cometric association scheme, In preparation.
  • [19] H. Maruri–Aguilar, H. P. Wynn, Algebraic Method in Experimental Design, pp. 415–454. In: Handbook of Design and Analysis of Experiments (1st Ed.) Chapman & Hall/CRC Handbooks of Modern Statistical Methods, Boca Raton, 2015.
  • [20] H. M. Möller, On the construction of cubature formulae with few nodes using Groebner bases, pp. 177–192 in: Numerical integration (Halifax, N.S., 1986) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 203, Reidel, Dordrecht, 1987.
  • [21] D. K. Ray-Chaudhuri, R. M. Wilson, On t-designs, Osaka J. Math. 12(3) (1975) 737–744.
  • [22] D. R. Stinson, Y. J. Wei, Some results on quadrilaterals in Steiner triple systems, Discrete Math. 105(1–3) (1992) 207–219.
  • [23] D. R. Stinson, Combinatorial Designs: Constructions and Analysis, Springer, New York, 2004.
  • [24] T. Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. EMS Surv. Math. Sci. 1 (2014) 1–46.
Primary Language en
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0002-2027-5859
Author: William J. MARTIN
Institution: Worcester Polytechnic Institute
Country: United States


Orcid: 0000-0001-5635-8122
Author: Douglas R. STINSON
Institution: University of Waterloo
Country: Canada


Dates

Publication Date : May 7, 2020

Bibtex @research article { jacodesmath729446, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2020}, volume = {7}, pages = {161 - 181}, doi = {10.13069/jacodesmath.729446}, title = {Some bounds arising from a polynomial ideal associated to any \$t\$-design}, key = {cite}, author = {J. Martın, William and R. Stınson, Douglas} }
APA J. Martın, W , R. Stınson, D . (2020). Some bounds arising from a polynomial ideal associated to any $t$-design . Journal of Algebra Combinatorics Discrete Structures and Applications , 7 (2) , 161-181 . DOI: 10.13069/jacodesmath.729446
MLA J. Martın, W , R. Stınson, D . "Some bounds arising from a polynomial ideal associated to any $t$-design" . Journal of Algebra Combinatorics Discrete Structures and Applications 7 (2020 ): 161-181 <https://dergipark.org.tr/en/pub/jacodesmath/issue/54201/729446>
Chicago J. Martın, W , R. Stınson, D . "Some bounds arising from a polynomial ideal associated to any $t$-design". Journal of Algebra Combinatorics Discrete Structures and Applications 7 (2020 ): 161-181
RIS TY - JOUR T1 - Some bounds arising from a polynomial ideal associated to any $t$-design AU - William J. Martın , Douglas R. Stınson Y1 - 2020 PY - 2020 N1 - doi: 10.13069/jacodesmath.729446 DO - 10.13069/jacodesmath.729446 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 161 EP - 181 VL - 7 IS - 2 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.729446 UR - https://doi.org/10.13069/jacodesmath.729446 Y2 - 2019 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications Some bounds arising from a polynomial ideal associated to any $t$-design %A William J. Martın , Douglas R. Stınson %T Some bounds arising from a polynomial ideal associated to any $t$-design %D 2020 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 7 %N 2 %R doi: 10.13069/jacodesmath.729446 %U 10.13069/jacodesmath.729446
ISNAD J. Martın, William , R. Stınson, Douglas . "Some bounds arising from a polynomial ideal associated to any $t$-design". Journal of Algebra Combinatorics Discrete Structures and Applications 7 / 2 (May 2020): 161-181 . https://doi.org/10.13069/jacodesmath.729446
AMA J. Martın W , R. Stınson D . Some bounds arising from a polynomial ideal associated to any $t$-design. Journal of Algebra Combinatorics Discrete Structures and Applications. 2020; 7(2): 161-181.
Vancouver J. Martın W , R. Stınson D . Some bounds arising from a polynomial ideal associated to any $t$-design. Journal of Algebra Combinatorics Discrete Structures and Applications. 2020; 7(2): 161-181.