$k$-regular linear set systems

Question

For any set $X$ and cardinal $\kappa$, we denote by $\ [X]^\kappa :=\ \binom X\kappa\ $ the collection of subsets of $X$ having cardinality $\kappa$.

If $X$ is a set, we call a set system $E\subseteq {\cal P}(X)$ linear if for all $a\neq b\in X$ there is exactly one $e\in E$ with $\{a,b\}\subseteq e$. For example, for every set $X$, the set system $[X]^2$ is linear.

For which integers $k\in \omega$ with $k > 2$ is there a linear set system $E\subseteq [\omega]^k$?

Answer 1

I think they exist for all $k \geq 2$. Here is a proof. Fix an enumeration of $[\omega]^2$. For the first step in the process add an arbitrary $k$-set $q_1=q(p_1)$ containing the first pair $p_1$ of the enumeration. At step $i$, if $\ p_i\subseteq q(p_j)\ $ for some $\ j<i\ $ then let $\ q(p_i):=q(p_j).\ $ Otherwise, select any $(k-2)$-set $\ r\subseteq \omega\setminus p_i\ $ that is not contained in $\, \bigcup_{t=1}^{i-1}\,q(p_t),\ $ and let

$$ q(p_i)\ :=\ p_i\cup r $$

for every $\ i>1.\ $ Then $\ E\ :=\ \{q(p_i):\ i\in\mathbb N\}\ $ is the solution.

Answer 2

EXAMPLE    for $\ \kappa=3:$

$$ E\ :=\ \left\{t\in\binom \omega3:\ \bigoplus t\ =\ 0\right\} $$

where each binary digit of $\ \bigoplus t\ $ is the mod 2 sum (EXCLUSIVE OR) of the three respective binary digits of the members of $\ t\in\binom \omega3.$

Here, it is $\ \omega\ :=\ \{x\in\mathbb Z: x\ge 1\}\ $ -- it's important only that $\ \omega\ $ is infinite and countable.

Answer 3

EXAMPLE    for $\ \kappa=4\, :$

We can replace $\ \omega\ $ by arbitrary set $\ V\ $ such that $\ |V|=|\omega|.\ $ Thus, let $\ V\ $ be a linear space over $4$-element field (such that $\ |V|=|\omega|;\ $ e.g. can be the set of all sequences of elements of $\ F,\ $ indexed by $\ \mathbb N,\ $ that are extensions of such finite sequences by an infinite tail of $0$'s).

Let $\ i\ $ and $\ j\ $ be the two different elements of $\ F\ $ that both are different from $0$ and $1$.

Then, arbitrary different elements $\ a\ $ and $\ b\ $ of $\ V\ $ form an unordered pair that can be extended by another pair:

$$ c:=i\cdot a + j\cdot b\qquad\text{and}\qquad d:=j\cdot a + i\cdot b $$

Then $$ c+d\ =\ (i+j)\cdot(a+b)\ \ne\ 0 $$ hence $\ c\ne d.\ $

Also, $$ a+c\ =\ a\ +\ (i\cdot a + j\cdot b)\ =\ j\cdot(a+b) \ \ne\ 0 $$ hence $\ a\ne c,\ $ and proofs of $\ a\ne d\ $ and $\ b\ne c\ $ and $\ b\ne d\ $ are similar. Thus, we have obtained a quadruple of four different elements. Call this quadruple rhombus $\ \mathcal R.\ $

---

It turns out rhombus $\ \mathcal R\ $ can be obtained in this way from its arbitrary pair of different elements (all six constructions give the same result $\ \mathcal R);\ $ indeed:

$$ i\cdot c\ +\ j\cdot d\ =\ (j\cdot a+ b)\ +\ (i\cdot a+b)\ = \ (j+i)\cdot a\ =\ a $$ i.e. $\,\ i\cdot c\ +\ j\cdot d\ =\ a,\,\ $ as well as

$$ j\cdot c\ +\ i\cdot d\ =\ (a+i\cdot b)\ +\ (a+j\cdot b)\ = \ (i+j)\cdot b\ =\ b $$ i.e. $\ j\cdot c\ +\ i\cdot d\ =\ b.$

The remaining four cases (of the six) are even easier to view:

$$ i\cdot a\ +\ j\cdot c\ =\ i\cdot a\ +\ (a+i\cdot b)\ = \ j\cdot a\ +\ i\cdot b\ =\ d $$ i.e. $\,\ i\cdot a\ +\ j\cdot c\ =\ d,\,\ $ as well as

$$ j\cdot a\ +\ i\cdot c\ =\ j\cdot a+(j\cdot a + b)\ =\ b $$ i.e. $\,\ j\cdot a\ +\ i\cdot c\ =\ b.$

We have proven the third case. The remaining three (of the six) are similar.

This proves that set $\ E\ $ of all rhombi $\ \mathcal R\in\binom V4\ $ is linear   (one could say: half-projective).

---

---

Best regards,

    Włodzimierz Holsztyński

---

Answer 4

AFFINE and PROJECTIVE SPACES

Let $\ X\ $ be an affine or a projective space (of arbitrary dimension), say, over a field $\ F\ $. Then every straight line $\ L\ $ of $\ X\ $ has cardinality equal to $\ \kappa:=|F|\ $ or $\ \kappa:=|F|+1\ $ respectively (these affine and projective cardinalities differ by $\ 1\ $ iff $\ F\ $ is finite). The set $\ E\subseteq \binom X\kappa\ $ of all straight lines in $\ X\ $ is linear and provides a solution to the OP question, when $\ |X|=|\omega|.$

-- Thus, there are two solutions for every finite field $\ F\ $, i.e. there are solutions for each $\ \kappa=p^n\ $ and each $\ \kappa=p^n+1\ $ where $\ p\ $ is an arbitrary prime and $\ n\in\mathbb N\ $ is an arbitrary natural number.

There are also two solutions for each field $\ F\ $ such that $\ |F|=|X|=|\omega|,\ $ -- for instance, let $\ F=\mathbb Q\ $ be the field of rational numbers, etc. Then $\ \kappa=|\omega|.$

---

These finite algebraic examples of $\ \kappa\ $ start with all

$$ 2\ \le\ \kappa\ \le\ 14 $$

followed by $$ 16 \le\ \kappa\ \le\ 20 $$ followed by $$ 23 \le\ \kappa\ \le\ 33 $$

etc. Some of these $\ \kappa\ $ are affine, some are projective, and some -- but very few -- are both, e.g.

$$ 2^2=3+1\qquad 5=2^2+1\qquad 2^3=7+1\qquad 3^2=2^3+1\qquad 17=2^4+1 $$

etc., in particular, Fermat primes are both; and so $\ \kappa=M+1\ $ where $\ M\ $ is a Mersenne prime. However, as it is well known, there is only one solution to $\ |p^n-q^m|=1,\ $ where $\ p\ $ and $\ q\ $ are primes, and natural numbers $\ n\ $ and $\ m\ $ are both greater than $1$ (this a special case of the respective Tijdeman's theorem). Thus, for $\ \kappa>17\ $ only the Fermat and Mersenne cases remain.