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$ Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$ Commented Jul 12, 2016 at 15:47
  • $\begingroup$ Since every 2-face belongs to three 3-faces it is not a manifold. $\endgroup$
    – Gil Kalai
    Commented Jul 12, 2016 at 20:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .