2
$\begingroup$

This question is inspired by the discussion at this problem.

Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called blocks) $X_i$ for $i \in [n]=\{1,2,\dots,n\}$ each with complement $\overline{X_i}$ and size $|X_i|=m_i=m_{\{i\}}$. Then there are $2^n$ values indexed by the subsets of $[n]$ $$m_I=|\cap_{i \in I}X_i|$$

and another $2^n$ values defined by $$t_I=|(\cap_{i \in I}X_i)\cap(\cap_{j \notin I}\overline{X_{j}})|$$ The $m$ values arise from the $t$ by simple addition and the $t$ values from the $m$ by inclusion-exclusion.

$$m_I=\sum_{I \subseteq J \subseteq [n]}t_J\hspace{0.1in} \text{ while } t_I=\sum_{I \subseteq J \subseteq [n]}(-1)^{|J|-|I|}m_J$$

In this setting the values are all non-negative reals which happen to be integers. Give all $2^n$ values we can recreate the structure up to isomorphism by assigning $|t_I|$ points for each non-zero $t_I$. This is essentially making an imaginary Venn diagram for the $n$ sets and noting the number of points in each small region.

If we only have partial information then it may be harder to recover the design. For lack of a better idea let me call such a description a design constraint system.. It consists of some number of assigned values $m_I$ in $\mathbb{N}$ and the challenge is to find $2^n$ non-negative integer $t_I$ values which realize it.

For example, suppose I give this system of $22$ constraints:

$m_{\emptyset}=8$, $m_i=4$ for $1 \le i \le 6$ and $m_{\{i,j\}}=2$ except $m_{\{1,2\}}=m_{\{3,4\}}=m_{\{5,6\}}=0.$

In other words, I tell you that I have $8$ points falling into $6$ blocks each of size $4$ and every pair of blocks intersects in $2$ points except that $|X_1 \cap X_2|=|X_3 \cap X_4|=|X_5 \cap X_6|=0.$ I am thinking of the $6$ faces of a cube but there is one other legitimate solution: perhaps there are $8$ people belonging to $4$ couples and the blocks of the design consist of all ways that $4$ people can go on a double date each person with their partner.

Over the non-negative reals there is a one parameter family of solutions. All the $t_I$ where $I$ has at least $4$ members are forced to be zero as are $12$ of the $20$ values $t_{\{i,j,k\}}.$ Of the other 8, half are $x$ and the other half $2-x.$

If we allow negative $t$ values then we can we can arbitrarily assign values to the other $2^6-22=42$ of the $m_I$ values and arrive at a unique set of $t_I$ values.

A projective plane of order $q$ could be defined as a design with $n=q^2+q+1$ blocks and an equal number $m_{\emptyset}=n$ of points. All $n$ blocks each of size $m_i=q+1$ and all pairwise intersections of size $m_{\{i,j\}}=1.$ It is unknown if any solutions exist in the case $q=12$ or, indeed, for any $q$ which is not a prime power. Again it is trivial to satisfy these $1+n+\binom{n}{2}$ constraints using arbitrary reals, but what about non-negative reals? More generally:

Given a design constraint system with all constraints in $\mathbb{N}$, if there is a real solution with $2^n$ non-negative $t_I$ values, must there be one with non-negative integer $t$ values? Is there any example where there is a real solution but not known to be an integer solution?

$\endgroup$
1
  • $\begingroup$ Now that I have written this, I think perhaps the answers are yes and no from imagining the sytem as a (very!) huge linear program with $2^n$ variables and considering when the simplex method would pivot as it sought a solution. If so, is there an explanation with less machinery involved? $\endgroup$ Apr 2, 2012 at 18:07

1 Answer 1

0
$\begingroup$

In spite of my comment, in fact a non-negative rational solution need not imply a non-negative integer solution. There are no projective planes of order $q=6$ (nor $q=10$) but there is a non-negative rational solution to the constraints for any $q$

Recall that the constraints for a projective plane of order $q$ are:

A universe of $m_{\emptyset}=q^2+q+1$ points and an equal number $n=q^2+q+1$ of blocks (usually called lines) each with $m_i=q+1$ points $1 \le i \le n$ and all $\binom{n}{2}$ pairwise intersections of size $m_{\{i,j\}}=1.$

In a legitimate projective plane each point is on $q+1$ lines so $t_I=0$ for all $I$ with the exception of a certain $n$ sets , each of size $q+1$, with $t_J=1.$ However we can obtain a rational solution by setting all the $t_I=0$ except that every one of the $\binom{n}{q+1}$ sets of size $q+1$ has $t_J=1/\binom{n-2}{q-1}.$ This, of course, makes all the $m_{\{i,j\}}=1$ and it is easy to verify that

$$m_{\emptyset}=\frac{\binom{n}{q+1}}{\binom{n-2}{q-1}}=n, \hspace{0.2in} m_i=\frac{\binom{n-1}{q}}{\binom{n-2}{q-1}}=q+1.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.