Skip to main content
edited body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(t,v,k,\lambda)$$(v,k,t,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$-element set $X$ such that every $t$-subset of $X$ is contained in exactly $\lambda$ blocks. You are interested in the case $t=\lambda=2$. There are some obvious divisibility conditions. For example, $\binom{k}{2}$ must divide $\lambda \binom{v}{2}$. Moreover, the condition on pairs also implies that the number of blocks containing a single element is also constant. So, $k-1$ must also divide $\lambda (v-1)$. It was a famous open problem called the Existence Conjecture, whether these divisibility conditions were also sufficent (up to a finite number of counterexamples). In a series of influential papers in the 1970s, Richard Wilson solved the Existence Conjecture for $t=2$. Recently, Peter Keevash solved the Existence Conjecture in general. See the paper The existence of designs and the references therein.

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(t,v,k,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$-element set $X$ such that every $t$-subset of $X$ is contained in exactly $\lambda$ blocks. You are interested in the case $t=\lambda=2$. There are some obvious divisibility conditions. For example, $\binom{k}{2}$ must divide $\lambda \binom{v}{2}$. Moreover, the condition on pairs also implies that the number of blocks containing a single element is also constant. So, $k-1$ must also divide $\lambda (v-1)$. It was a famous open problem called the Existence Conjecture, whether these divisibility conditions were also sufficent (up to a finite number of counterexamples). In a series of influential papers in the 1970s, Richard Wilson solved the Existence Conjecture for $t=2$. Recently, Peter Keevash solved the Existence Conjecture in general. See the paper The existence of designs and the references therein.

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(v,k,t,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$-element set $X$ such that every $t$-subset of $X$ is contained in exactly $\lambda$ blocks. You are interested in the case $t=\lambda=2$. There are some obvious divisibility conditions. For example, $\binom{k}{2}$ must divide $\lambda \binom{v}{2}$. Moreover, the condition on pairs also implies that the number of blocks containing a single element is also constant. So, $k-1$ must also divide $\lambda (v-1)$. It was a famous open problem called the Existence Conjecture, whether these divisibility conditions were also sufficent (up to a finite number of counterexamples). In a series of influential papers in the 1970s, Richard Wilson solved the Existence Conjecture for $t=2$. Recently, Peter Keevash solved the Existence Conjecture in general. See the paper The existence of designs and the references therein.

edited body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(t,v,k,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$-element set $X$ such that every $t$-subset of $X$ is contained in exactly $\lambda$ blocks. You are interested in the case $t=\lambda=2$. There are some obvious divisibility conditions. For example, $\binom{k}{2}$ must divide $\lambda \binom{v}{2}$. Moreover, the condition on pairs also implies that the number of blocks containing a single element is also constant. So, $k-1$ must also divide $\lambda (v-1)$. It was a famous open problem called the Existence Conjecture, whether these divisibility conditions were also sufficent (up to a finite number of counterexamples). In a series of influential papers in the 1970s, Richard Wilson solved the Existence conjectureConjecture for $t=2$. Recently, Peter Keevash solved the Existence conjectureConjecture in general. See the paper The existence of designs and the references therein.

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(t,v,k,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$-element set $X$ such that every $t$-subset of $X$ is contained in exactly $\lambda$ blocks. You are interested in the case $t=\lambda=2$. There are some obvious divisibility conditions. For example, $\binom{k}{2}$ must divide $\lambda \binom{v}{2}$. Moreover, the condition on pairs also implies that the number of blocks containing a single element is also constant. So, $k-1$ must also divide $\lambda (v-1)$. It was a famous open problem called the Existence Conjecture, whether these divisibility conditions were also sufficent (up to a finite number of counterexamples). In a series of influential papers in the 1970s, Richard Wilson solved the Existence conjecture for $t=2$. Recently, Peter Keevash solved the Existence conjecture in general. See the paper The existence of designs and the references therein.

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(t,v,k,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$-element set $X$ such that every $t$-subset of $X$ is contained in exactly $\lambda$ blocks. You are interested in the case $t=\lambda=2$. There are some obvious divisibility conditions. For example, $\binom{k}{2}$ must divide $\lambda \binom{v}{2}$. Moreover, the condition on pairs also implies that the number of blocks containing a single element is also constant. So, $k-1$ must also divide $\lambda (v-1)$. It was a famous open problem called the Existence Conjecture, whether these divisibility conditions were also sufficent (up to a finite number of counterexamples). In a series of influential papers in the 1970s, Richard Wilson solved the Existence Conjecture for $t=2$. Recently, Peter Keevash solved the Existence Conjecture in general. See the paper The existence of designs and the references therein.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(t,v,k,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$-element set $X$ such that every $t$-subset of $X$ is contained in exactly $\lambda$ blocks. You are interested in the case $t=\lambda=2$. There are some obvious divisibility conditions. For example, $\binom{k}{2}$ must divide $\lambda \binom{v}{2}$. Moreover, the condition on pairs also implies that the number of blocks containing a single element is also constant. So, $k-1$ must also divide $\lambda (v-1)$. It was a famous open problem called the Existence Conjecture, whether these divisibility conditions were also sufficent (up to a finite number of counterexamples). In a series of influential papers in the 1970s, Richard Wilson solved the Existence conjecture for $t=2$. Recently, Peter Keevash solved the Existence conjecture in general. See the paper The existence of designs and the references therein.