2

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?

flag
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? – Aaron Meyerowitz Apr 2 2012 at 18:07

1 Answer

0

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

link|flag

Your Answer

Get an OpenID
or

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