Imagine a set of vertices $V$ of a size $n$. Let $E=\binom{V}{2}$ be all possible edges between those vertices. Consider $$M = \{\{a,b\}-\{b,c\}\ |\ a,b,c\in V, a\neq b\neq c\} \subset \mathbb Z^E.$$ Question: what is the minimal subset $M'$ of $M$ such that $\text{span}(M') \supset M$?
Now, I am first going to rephrase the task in more human words: imagine you have $n$ variables, and you construct expressions of the form $\frac{a+b}{b+c}$. What is the minimal possible amount of these expressions, such that any other expression of that form can be constructed from those using just multiplication and multiplicative inverse?
OK, now I will write some ideas I had:
- $|E| = \frac{n\cdot (n-1)}{2}$, $|M| = n\cdot (n-1) \cdot (n-2)$.
- assuming it is not $\mathbb Z$ in the definition of $M$, but $\mathbb F_2$ or $\mathbb R$ or any other reasonable field, we can use some dimension arguments to show that dimension of $\text{span}(M)$ is less than $|E|-1$, hence the approximate answer to aim for is somewhere below $\frac{n\cdot (n-1)}{2}$.
- I can construct $M'$ of size $n\cdot (n-2)$, which can be slightly optimized further: $M' = \{\{a,b\}-\{b,c\}\ |\ a = \pi(b)\}$ where $\pi$ is some permutation on $V$ without fixed points.
- UPD: here is some optimization of my method: Say $V = \{v_1,v_2,\ldots,v_n\}$ and also $v_0 = v_n$. Take $$M' = \{\{v_{i-1},v_{i}\}-\{v_i,v_k\}\ |\ 0<i<k\leq n\}\setminus\{0\}.$$ We exclude $0$ because $\{v_{0},v_{1}\}-\{v_1,v_n\} = 0$. Such an $M'$ has the size of exactly $\frac{n\cdot (n-1)}{2}-1$.
P.S. I am not sure if the title describes my question well enough, so if you got a better title feel free to edit it. Same with tags.
The answer is almost already contained in the question; you just have to “reverse” the dimensional argument. You can't do any better than $|M'|=|E|-1$, since $M$ spans the entire orthogonal complement of the constant vector in $\mathbb R^E$, so it contains $|E|-1$ linearly independent vectors, and restricting your coefficients to integers doesn't change the fact that you need at least $|E|-1$ vectors to span $|E|-1$ linearly independent vectors.