Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 88 / 4

Use octahedral quasirandomness of a three-uniform hypergraph, with its eighth-power normalization. Let $h:X\times Y\times Z\to \{0,1\}$ be the hypergraph edge indicator function, define $p={\mathbb{E}}_{x,y,z}h(x,y,z)$, and put $g=h-p$. All expectations are uniform and independent on the indicated finite sets. The hypergraph is $\alpha$-quasirandom whenThe eight triples form the faces of the tripartite octahedral configuration. Repeated choices within a part are included in this normalized average. For real $g$, the expression is nonnegative, since it equalsThus the condition says that the balanced hypergraph edge indicator function has three-dimensional box norm at most ${\alpha }^{1/8}$. If the norm itself is used as the quasirandomness parameter instead, the eighth-power parameter here is the eighth power of that parameter; stating this convention fixes the quantitative meaning of the counting error.

First prove the pair-factor correlation bound for the three-dimensional box norm. For real $g$ and three functions $a(y,z),b(x,z),c(x,y)$ bounded in absolute value by one, letApply the Cauchy-Schwarz inequality in $(y,z)$, placing the $x$ average inside and removing $a$. This givesExpand this square, with independent $x_0,x_1$. Apply Cauchy-Schwarz in $(x_0,x_1,z)$, removing the product $b(x_0,z)b(x_1,z)$. The result isExpand with independent $y_0,y_1$ and apply Cauchy-Schwarz in $(x_0,x_1,y_0,y_1)$, removing the four $c$ factors. ThenTherefore $|T|\le \Vert g{\Vert }_{{\square }^3}$, with no independence assumption on the three pair functions.

In this multipartite hypergraph, a simplex is a three-uniform tetrahedron: one vertex of a hypergraph from each of $X,Y,Z,W$, with all four possible triples present. Write the corresponding hypergraph edge indicator functions as $h_1(x,y,z),h_2(x,y,w),h_3(x,z,w),h_4(y,z,w)$, of subset densities $p,q,r,s$. Its normalized count isTelescope the product exactly:For the first term fix $w$. The remaining three factors are bounded pair functions of $(x,y)$, $(x,z)$ and $(y,z)$, so the inequality just proved bounds its $(x,y,z)$ average by $\Vert h_1-p{\Vert }_{{\square }^3}\le {\alpha }^{1/8}$. Averaging over $w$ preserves that bound. For each other term fix the vertex of a hypergraph outside its balanced triple and apply the same argument, allowing an unused pair factor to be identically one. The subset density prefactors are at most one. HenceMultiplying by $|X||Y||Z||W|$ givesThus one may take the absolute constant $C=4$. This proves the complete-pair-support case of the tetrahedron counting lemma directly; no lower bound on $p,q,r,s$ is needed.

Yes. The same telescoping argument proves the counting lemma for octahedrally quasirandom three-uniform hypergraphs for every fixed simple three-uniform hypergraph $F$.

Label its vertices of a hypergraph $1,\dots ,v$ and give vertex of a hypergraph $i$ a nonempty host part $V_i$. For each hypergraph edge $e=\{i,j,k\}$, let $h_e$ be the corresponding host hypergraph edge indicator function of subset density $p_e$, with $\Vert h_e-p_e{\Vert }_{{\square }^3}\le {\alpha }^{1/8}$. The normalized labelled hypergraph copy count isIf the host parts are disjoint, every such vertex of a hypergraph choice is automatically injective. Enumerate the $m$ hypergraph edges as $e_1,\dots ,e_m$ and telescopeIn the term for $e_j=\{a,b,c\}$, fix all variables outside this triple. Since $F$ is simple and three-uniform, every other hypergraph edge intersects $\{a,b,c\}$ in at most two vertices of a hypergraph. Its remaining factor therefore depends on at most two of $x_a,x_b,x_c$. Group all two-variable factors according to the pairs $(a,b),(a,c),(b,c)$. Absorb each one-variable factor into any pair containing its variable, and constants into any group. The three resulting pair functions remain bounded by one.

The balanced factor is now multiplied by exactly the sort of pair functions handled in part (ii). Its average has absolute value at most ${\alpha }^{1/8}$, independently of the fixed outside variables. Averaging those variables and summing the $m$ errors givesEquivalently,This counts labelled copies preserving the specified vertex of a hypergraph classes, for arbitrary intersection patterns among the hypergraph edges, and includes the three-uniform tetrahedron as a special case.

For a common host vertex of a hypergraph set of size $n$, the same product average counts homomorphisms. At most $\left(\genfrac{}{}{0ex}{}{v}{2}\right)n^{v-1}$ assignments identify a pair of distinct labelled vertices of a hypergraph, by the union bound. Thus restricting to injective copies changes the estimate by at most this amount. With a common normalized subset density $p$ the injective count is therefore $p^m{n}^v+O(m{\alpha }^{1/8}{n}^v+v^2{n}^{v-1})$. For induced copies, include the nonhypergraph edge indicator functions as additional factors; their balanced functions are negatives of the corresponding edge-balanced functions and have the same box norm. The same proof applies provided all the relevant triple parts satisfy the stated quasirandomness condition.