By a $d$-permutation hypergraph, I mean, for some fixed integer $k$, a $d$-uniform hypergraph on $[dk]$ with $k$ disjoint edges such that every edge has exactly one vertex from each of $\{1,\ldots,k\}$, $\{k+1,\ldots,2k\}$, $\ldots$, and $\{(d-1)k+1,\ldots,dk\}$. (So each vertex is contained in exactly one edge.)


By containment I mean that $G$ contains $H$ if we have an increasing injection $V(H)\to V(G)$ and an injection $E(H)\to E(G)$ that are compatible (that is, if $E$ is sent to $E'$, the vertices of $E$ are sent to (some of) the vertices of $E'$). In case it isn't clear, $n$ is allowed to vary and $d$ is fixed in this problem.


This, if true, generalizes two results of Klazar and Marcus in <https://arxiv.org/abs/math/0507164>; Section 2 proves the statement when $d=2$ and Section 3 proves (or nearly proves proves) the case where the containing hypergraph is restricted to be $d$-uniform.



Is an $O(n^{d-1})$ bound known for the maximum number of edges in an ordered $n$-vertex hypergraph avoiding a fixed $d$-permutation hypergraph?
Yes, the $O(n^{d-1})$ bound holds in this case as well, with a proof that is similar to the proof of the $d$-uniform case.
I would guess that this also follows from the proof of Klazar and Marcus with some easy modification, but I don't know it as well as our own proof, which you can find in Section 3 here:
<https://arxiv.org/pdf/1408.4093.pdf>.


First, make a $d$-uniform hypergraph $G'$ from $G$ by picking a set of size $d$ from each hyperedge.
The choice is arbitrary, except that we try to maximize the number of edges of $G'$.
In particular, if a hyperedge $e$ of $G$ is mapped to a hyperedge of $G'$ into which another edge of $G$ is also mapped, then all $d$-element subsets of $e$ are also in $G'$.
If this happens for a hyperedge $e$ of size at least $kd$, we are done, as we can find $H$ inside $e$.
Because of this, we can suppose that $G$ is uniform.
The bound trivially holds for $(d-1)$-uniform hypergraphs.
The rest of the proof is partly by induction, partly by repeating the argument for $d$-uniform hypergraphs.


**Proof for $t$-uniform hypergrahs.**


If $G$ has $n$ vertices, then we divide these vertices into intervals of length $s$, where $s$ is a constant that is large enough compared to $k,d$ and $t$.
Denote by $E\_0$ the edges of $G$ that have at least two vertices in the same interval.
$|E\_0|\le C\_{t-1}n^{d-1}$ by induction.
(This is the only part where we use induction on $t$.)
Partition the rest of the edges of $G$ into $(\frac ns)^{t}$ blocks depending on which intervals the vertices belong to.
Denote the hyperedges of block $b$ by $E\_b$.
Define $Proj\_J$ as the projection that deletes the $j^{th}$ element of a hyperedge for every $j\in J$.
A block $b$ is $J$-wide if $Proj\_J E\_b$ contains $Proj\_i H$ for *every* $i\in \{1,\ldots,d\}$.
If $b$ is not $J$-wide for any $J\subset\{1,\ldots, t\}$ with $|J|=t-d+1$, then we call it thin.
We will prove by induction (on $d$) and the Loomis-Whitney inequality that $|E\_b|=o(s^{d-1})$ if $b$ is thin.
This will imply by contracting the intervals, the total number of edges in thin blocks is $o\_s(n^{d-1})$.


The Loomis-Whitney inequality says that $|E\_b|^{t-1}\le \Pi\_{j} |Proj\_j E\_b|$.
To obtain $|E\_b|=o(s^{d-1})$, it is enough to show for each $j$ that $|Proj\_j E\_b|=O(s^{d-2})$.
Otherwise, $Proj\_j E\_b$ would contain the hypergraph $Proj\_i H$ for every $i$.
From this we want to show for some $J$ that $Proj\_J E\_b$ would also contain them.
And now, it seems that I'll have to cheat a little; this statement would be trivial if by induction we were proving instead the stronger statement that there is a $|J|=t-d$ such that $Proj\_J G$ contains a copy of $H$.
But then we also have to verify this stronger statement in the earlier parts of this proof.
The estimate for $E\_0$ still holds, as if we had a lot of $j^{th}$ and $(j+1)^{st}$ vertices in the same interval, that would lead to induction as before.
I don't know how to fix the argument for hyperedges that are bigger than $kd$, but luckily that can be avoided; we only need to raise the bound of $kd$ to something that also depends on $t$.


The only thing left to estimate is the number of edges in $J$-wide blocks.
Group the blocks into $I$-blockcolumns where $I\subset\{1,\ldots, t\}$ with $|I|=d-1$; every block belongs to exactly $\binom{t}{d-1}$ blockcolumns.
An $I$-blockcolumn is determined by $d-1$ intervals, and it contains every block that is defined by these $d-1$ intervals (and $t-d+1$ other intervals).
If an $I$-blockcolumn contains more than $\big((k-1)^{t-d+1}-1\big)\big(s(s-1)\cdot (s-k+1)\big)^{d(d-1)}$ $J$-wide blocks, then by the pigeonhole principle it contains $(k-1)^{t-d+1}$ blocks such that for $J=\{1,\ldots,t\}\setminus I$ the hypergraphs $Proj\_J E\_b$ contain the same copy of $Proj\_i H$ for each $i\in\{1,\ldots,d\}$.
(These copies are all inside the $d-1$ intervals defining the $I$-blockcolumn.)
Using the pigeonhole principle again, for some $j\in J$ there are at least $k$ different intervals that contain the $j^{th}$ vertices of these blocks.
But then from any $k$ blocks that use these $k$ intervals and have the same copy of the respective $Proj\_i H$, we can build a copy of $H$ in $G$.


Therefore, the number of $i$-wide blocks is small and the rest is calculation.


