Research Article
BibTex RIS Cite
Year 2020, , 161 - 181, 07.05.2020
https://doi.org/10.13069/jacodesmath.729446

Abstract

References

  • [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.

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

Year 2020, , 161 - 181, 07.05.2020
https://doi.org/10.13069/jacodesmath.729446

Abstract

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$.

References

  • [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.
There are 24 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

William J. Martın This is me 0000-0002-2027-5859

Douglas R. Stınson This is me 0000-0001-5635-8122

Publication Date May 7, 2020
Published in Issue Year 2020

Cite

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. 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. May 2020;7(2):161-181. doi:10.13069/jacodesmath.729446
Chicago J. Martın, William, and Douglas R. Stınson. “Some Bounds Arising from a Polynomial Ideal Associated to Any $t$-Design”. Journal of Algebra Combinatorics Discrete Structures and Applications 7, no. 2 (May 2020): 161-81. https://doi.org/10.13069/jacodesmath.729446.
EndNote J. Martın W, R. Stınson D (May 1, 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.
IEEE W. J. Martın and D. R. Stınson, “Some bounds arising from a polynomial ideal associated to any $t$-design”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 7, no. 2, pp. 161–181, 2020, doi: 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.
JAMA 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:161–181.
MLA J. Martın, William and Douglas R. Stınson. “Some Bounds Arising from a Polynomial Ideal Associated to Any $t$-Design”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 7, no. 2, 2020, pp. 161-8, doi:10.13069/jacodesmath.729446.
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-8.