10
$\begingroup$

This question was raised from a project with Nati Linial and Yuval Peled

We are seeking a $3$-dimensional simplicial complex $K$ on $12$ vertices with the following properties

a) $K$ has a complete $2$-dimensional skeleton (namely, every triple of vertices form a 2-face of $K$) and it has $165$ $3$-simplices.

b) Every $2$-face belongs to three $3$-faces

c) Every $1$-face belong to fifteen $3$-faces

d) Every vertex belongs to fifty five $3$-faces.

e) $H_3(K,\mathbb Z)=0$.

While all these properties are little negotiable we can ask even that $K$ would admit further interesting symmetries and regularity properties.

By property 2, the list of $3$-faces of $K$ is a $3$$-$$(12,4,3)$ design. So perhaps such an example can be found among the known designs.

We can hope, more geneally, for $\mathbb Q$-acyclic $k$-dimensional simplicial complexes $K$ on $n=k(k+1)$ vertices with complete $(k-1)$-skeleta and with similar regularity properties. Namely, $K$ must have ${{n-1}\choose {k-1}}$ $k$-faces, and we can demand that every $(k-1)$-face belongs to $k$ $k$-faces, and more generally that every $i$-face $i <k$ belongs to the same number of $k$-faces.

The only example I know is, for $k=2$, the $6$-vertex triangulation of $RP^2$.

$\endgroup$
1
  • $\begingroup$ Does it provide any additional insight (or make sense at all) to dualize and shift up by one? The result would have (?) vertices, 165 edges, all 2-faces triangles, all 3-faces with 15 edges, twelve 4-faces with 55 edges, and every triple of 4-faces meeting at a 2-face... $\endgroup$ Jul 30, 2016 at 19:02

2 Answers 2

8
+150
$\begingroup$

Here's at least a couple of candidate designs which have the first four properties, although I haven't checked acyclicity and don't yet see how to exploit the existing symmetries to check it other than by a brute-force rank computation of the boundary map.

(1) The orbit of the set $\{ \infty, 0, 1, 2 \}$ under the fractional-linear action of $G=\mathrm{PSL}_2(11)$ on $\mathbb{Z}/11\mathbb{Z} \cup \{ \infty \}$ gives a $3$-$(12,4,3)$ design, which we can decorate with orientations to pass from subsets to simplices to chains. The $15$ blocks containing the $1$-face $\{ \infty, 0 \}$ induce a bipartite $3$-regular graph of order $10$ on the complement of this face; each edge of this graph connects a quadratic residue modulo $11$ to a non-residue (but not all such pairings occur); multiplication by the quadratic residue $3$ (which is in $G$ as $\mathrm{diag}(6,2)$) induces a symmetry of order $5$ on this graph. The $2$-face $F=\{ \infty, 0, 1 \}$ extends to the blocks $\{\infty 0 1 2\}$, $\{\infty 0 1 6\}$, $\{\infty 0 1 a\}$ (writing $a$ for the digit "10"), and the stabilizer in $G$ of $F$ as a set, generated by $x\mapsto 1-1/x$, permutes these blocks. And $G$ acts transitively on the $220$ three-element subsets, as well as on the two-element ones, so everything is as symmetric as one can hope for.

(2) Tung-Hsin Ku in Simple BIB Designs and 3-Designs of Small Orders (in W.D.Wallis et al (ed.), Combinatorial Designs and Applications, Lect. Notes in Pure and Applied Math. 126 (1990), 79-85) describes among others a $3$-$(12,4,3)$ design on the same set on which only $\mathbb{Z}/11\mathbb{Z}$ acts, leaving $\infty$ fixed. The blocks are $\{0 1 2 3\}$, $\{0 1 2 4\}$, $\{0 1 3 7\}$, $\{0 1 4 5\}$, $\{0 1 4 8\}$, $\{0 1 5 6 \}$, $\{0 1 6 9\}$, $\{0 2 4 6\}$, $\{0 2 5 7\}$, $\{0 2 5 8\}$, $\{0 1 5 \infty\}$, $\{0 1 8 \infty\}$, $\{0 1 9 \infty\}$, $\{0 2 5 \infty\}$, $\{0 2 7 \infty\}$ and their images under the group action. Here, proceeding as above, several different $3$-regular graphs of order $10$ occur among the complements of $1$-faces. Some of these graphs contain one or more triangles, but in no case are all five blocks present that would combine to the $3$-skeleton of a single $4$-simplex. (Which doesn't rule out more complicated cycles.)

Added 2016-07-30:

Computing the rank and the kernel of the boundary map in the two examples by brute force is unexciting but straightforward, so (for lack of a better idea and to see what would happen) I went through the exercise. It helps to organize the matrix as a 20-by-15 array of 11-by-11 circulants, most of which are zero and all of which are sparse.

If I didn't get any signs wrong, (1) indeed yields an acyclic complex (Edit 2016-08-02) a complex with $H_3(K,\mathbb{Z})=0$, $H_2(K,\mathbb{Q})=0$, and finite $H_2(K,\mathbb{Z})$. (Edit 2017-10-18) It seems I did get a sign wrong in one of the 11-by-11 circulants (and the first extra consistency check I thought of today but hadn't thought of last year immediately found it). Rerunning the rank computation, this example is now far from acyclic: the interesting boundary map has rank 155 instead of 165, thus both $H_3(K,\mathbb{Q})$ and $H_2(K,\mathbb{Q})$ will be 10-dimensional.

Ku's design (2) doesn't result in an acyclic complex; here I got $H_3(K,\mathbb{Z}) \cong \mathbb{Z}^2$. Generating cycles are sums over entire $\mathbb{Z}/11\mathbb{Z}$ orbits (and not involving the fixed point of the group action): $$\begin{gather} \{0145\}+\{1256\}+\dotsb-\{0148\}-\{1259\}-\dotsb+\{0156\}+\{1267\}+\dotsb; \\ \{0246\}+\{1357\}+\dotsb+\{0257\}+\{1368\}+\dotsb-\{0258\}-\{1369\}-\dotsb. \end{gather}$$ (Edit 2017-10-18) There might be a sign error here, too, affecting the outcome - there might be yet more cycles apart from the above. I don't have time to re-check this one right now.

Thus with a third of the 3-simplices taking part in the game, we seem to be near the border of where there are enough of them to combine into nontrivial cycles. I wouldn't be surprised if there were other solutions with fewer symmetries or with none at all.

(For comparison, the analogue of (1) using $\mathrm{PSL}_2(7)$ and the orbit of $\{\infty 012\}$ results in a $3$-$(8,4,3)$ design with $42$ blocks among the seventy $3$-simplices and an $H_3(K,\mathbb{Z})$ of rank $8$, spanned by the $24$-element orbit of $$\{0123\}+\{1234\}+\dotsb+\{6012\}+\{0134\}+\{1245\}+\dotsb+\{6023\},$$ which is again a sum over a whole orbit of the affine $\mathbb{Z}/7\mathbb{Z}$. Here we seem to have too many blocks to avoid such combinatorial coincidences. [Note that this is not the case $k=2$ of the question.])

A candidate for the case $k=4$, thus $n=20$, might be constructed in terms of $\mathrm{PSL}_2(19)$, remembering that the action by fractional linear transformations will be far from $4$-transitive; thus multiple orbits must be used to arrive at the desired $3876$ blocks. For $k=5$ and $k=6$, we also have convenient primes $29$ and $41$ to play this kind of game, moving even further beyond the available symmetries. But $55$ isn't prime, so a new idea would be needed for $k=7$.

Added 2017-10-17: By popular request, the 165 blocks for the first example arise from letting the affine $\mathbb{Z}/11\mathbb{Z}$ act on the 15 representatives $\{\infty 0 1 2\}$, $\{\infty 0 1 6\}$, $\{\infty 0 2 4\}$, $\{\infty 0 3 6\}$, $\{\infty 0 3 7\}$, $\{0 1 2 5\}$, $\{0 1 2 8\}$, $\{0 1 3 5\}$, $\{0 1 3 7\}$, $\{0 1 3 8\}$, $\{0 1 4 6\}$, $\{0 1 4 9\}$, $\{0 1 5 9\}$, $\{0 1 6 8\}$, $\{0 1 7 9\}$.

$\endgroup$
20
  • 1
    $\begingroup$ Why is the number of 3-cells in the orbit $165$? $\endgroup$
    – Will Sawin
    Jul 26, 2016 at 16:08
  • 1
    $\begingroup$ 165 3-cells in both cases. (Three for each of the 220 2-cells, and each 3-cells has four 2-faces.) In (1), the remaining 330 four-element subsets form another $G$-orbit. $\endgroup$
    – GNiklasch
    Jul 27, 2016 at 5:46
  • 1
    $\begingroup$ Good point @Gil - I had somehow talked myself into believing that $H_2$ would take care of itself, but that's true only for the rational homology. A partial computation suggests that $H_2(K,\mathbb{Z})$ is going to be (finite but) nontrivial, of order dividing $52073472$. $\endgroup$
    – GNiklasch
    Aug 2, 2016 at 8:09
  • 1
    $\begingroup$ No luck with $\mathrm{PSL}_2(19)$ though: The action on $5$-element subsets of the projective line does not seem to produce a $4$-design of the desired type, regardless of homology. Once I combine enough orbits to meet all $4$-elt subsets, some of them always end up in too many blocks. $\endgroup$
    – GNiklasch
    Aug 9, 2016 at 12:20
  • 1
    $\begingroup$ Hello @Gil, the existence of $4$-$(20,5,4)$ designs was an open question in 1983 (mentioned in a survey article by S.Kageyama and A.Hedayat), and my search-engine-fu has been too weak to find anything newer.- I'm not an expert on block designs; they're just something I had encountered (along with PGL/PSL group actions) in the late 1980s, coming from an algebraic number theory angle. $\endgroup$
    – GNiklasch
    Aug 11, 2016 at 10:15
1
$\begingroup$

This will be a short answer about where you cannot find such complexes. You mention symmetry, and it certainly seems like the typical such complex should be, say, vertex-transitive. But it follows from work of Smith and of Oliver that no $\mathbb{Q}$-acyclic complex admits a fixed-point-free action by any group which is the extension of a cyclic group by a $p$-group. So e.g. if $C$ is cyclic and $P$ is a $p$-group, then a desired complex can't admit fixed-point-free actions by groups of the form $C \times P$ or $C \rtimes P$.

In short, assuming the vertex-transitive or at least the fixed-point-free property, such a complex must have automorphism group which is (in the sense above) either fairly large or else fairly small.

See Robert Oliver, MR 375361 Fixed-point sets of group actions on finite acyclic complexes, Comment. Math. Helv. 50 (1975), 155--177.

$\endgroup$
4
  • $\begingroup$ Dear Russ, maybe we can base such a required complex on the icosahedron? $\endgroup$
    – Gil Kalai
    Jul 12, 2016 at 12:57
  • $\begingroup$ (Somehow I thought that having a vertex transitive group would imply an even number of 3-faces. but I am not sure now.) $\endgroup$
    – Gil Kalai
    Jul 12, 2016 at 14:38
  • $\begingroup$ Do you have any intuition as to what topological type one might expect? Most of the spaces that immediately come to mind are manifolds or closely related! $\endgroup$ Jul 12, 2016 at 15:47
  • $\begingroup$ Since every 2-face belongs to three 3-faces it is not a manifold. $\endgroup$
    – Gil Kalai
    Jul 12, 2016 at 20:14

Your Answer

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

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