Some results on $\lambda$-design conjecture

Document Type : Research Paper

Author

Department of Mathematics, St. Gonsalo Garcia College, University of Mumbai, India

10.22108/toc.2024.139121.2102

Abstract

Let $v$ and $\lambda$ be integers with $0<\lambda<v$. A $\lambda$-design $D$ is a pair $(X, \mathcal{A})$, where $X$ is a finite set with $v$ elements called points and $\mathcal{A}$ is a family of subsets of $X$ called blocks, with $|\mathcal{A}|=|X|$ such that

      (1) for all $B_i, B_j\in \mathcal{A},$ $i\neq j,$ $|B_i\cap B_j|=\lambda$;
      (2) for all $B_j\in \mathcal{A},$ $|B_j|=k_j>\lambda$, and not all $k_j$ are equal.

The only known examples of $\lambda$-designs are so called of type-1 designs, which are obtained from symmetric designs by a certain complementation procedure. Ryser and Woodall had independently conjectured that all $\lambda$-designs are of type-1. Suppose $r$ and $r^*(r>r^*)$ are replication numbers of $D$ and for distinct points $x$ and $y$ of $D$, let $\lambda(x,y)$ denote the number of blocks of $X$ containing $x$ and $y$.
 
In this paper we investigate the possibilities of $\lambda$-designs to be of type-1 under the condition that $|\lambda(x,y)-\lambda(x,y')|< 2 \left(\dfrac{r-r^*}{r+r^*-2}\right)$. Under this condition, we prove that if $ \dfrac{r-1}{r^*-1} \le 3$, then $\lambda$-design $D$ is of type-1. Also we prove that $D$ has exactly two distinct block sizes.

Keywords

Main Subjects


[1] T. Alraqad and M. S. Shrikhande. Some results on λ-designs with two block sizes, J. Combin. Des., 19 no. 2 (2011) 95–110.
[2] W. G. Bridges and E. S. Kramer, The determination of all λ-designs with λ = 3, J. Combinatorial Theory, 8 (1970) 343–349.
[3] W. G. Bridges, Some results on λ-designs, J. Combinatorial Theory, 8 (1970) 350–360.
[4] N. G. de Bruijn and P. Erdös, On a combinatorial problem, Indagationes Math., 10 (1948) 421–423.
[5] N. C. Fiala, Every λ-design on 6p + 1 points is type-1, Codes and designs (Columbus, OH, 2000), Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002 109–124.
[6] N. C. Fiala, λ-designs on 8p + 1 points, Ars Combin., 68 (2003) 17–32.
[7] N. C. Fiala, λ-designs with g = 7, Ars Combin., 97A (2010) 101–127.
[8] D. W. Hein and Y. J. Ionin, On the λ-design conjecture for v = 5p + 1 points, Codes and designs (Columbus, OH, 2000), Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002 145–156.
[9] Y. J. Ionin and M. S. Shrikhande, λ-designs on 4p+1 points, J. Combin. Math. Combin. Comput., 22 (1996) 135–142.
[10] Y. J. Ionin and M. S. Shrikhande, On the λ-design conjecture, J. Combin. Theory Ser. A, 74 no. 1 (1996) 100–114.
[11] Y. J. Ionin and M. S. Shrikhande, Combinatorics of symmetric designs, New Mathematical Monographs, 5, Cambridge University Press, Cambridge, 2006.
[12] E. S. Kramer, On λ-designs, Thesis (Ph.D.)–University of Michigan, ProQuest LLC, Ann Arbor, MI, 1969 pp. 86.
[13] E. S. Kramer, On λ-designs, J. Combinatorial Theory Ser. A, 16 (1974) 57–75.
[14] T. D. Parulekar and S. S. Sane, Some results on the Ryser design conjecture-III, J. Algebraic Combin., 55 (2020) 5–13.
[15] H. J. Ryser, An Extension of a Theorem of de Bruijn and Erdös on Combinatorial Designs, J. Algebra, 10 (1968) 246–261.
[16] A. Seress, All lambda-designs with λ = 2p are type-1, Des. Codes Cryptogr., 22 (2001) no. 1 5–17.
[17] N. M. Singhi and S. S. Shrikhande, On the λ-design conjecture, Utilitas Math., 9 (1976) 301–318.
[18] N. M. Singhi, M. S. Shrikhande and R. M. Pawale. Towards the Ryser-Woodall λ-design conjecture, J. Combin. Des., 31 (2023) no. 5 267–276
[19] S. S. Shrikhande and N. M. Singhi, Some combinatorial problems, Combinatorics and applications (Calcutta, 1982), Indian Statist. Inst., Calcutta, 1984 340–359.
[20] R. G. Stanton, Ryser designs, Ars Combinatoria, Ars Combin., 46 (1997) 133–144.
[21] I. Weisz, Lambda-designs with small lambda are type-1, Thesis (Ph.D.)–The Ohio State University, ProQuest LLC, Ann Arbor, MI, 1995 253 pp.
[22] D. R. Woodall, Square λ-linked designs, Proc. London Math. Soc. (3), 20 (1970) 669–687.
[23] A. K. Yadav, R. M. Pawale and M. S. Shrikhande, Exceptions and characterization results for type-1 λ-designs, J. Combin. Des., 28 no. 9 (2020) 670–687.
[24] A. K. Yadav, R. M. Pawale and M. S. Shrikhande, A note on λ-designs, J. Combin. Des., 28 no. 12 (2020) 893–899.
Volume 14, Issue 3 - Serial Number 3
September 2025
Pages 187-196
  • Receive Date: 14 September 2023
  • Revise Date: 06 February 2024
  • Accept Date: 13 August 2024
  • Published Online: 17 September 2024