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.

  • $\begingroup$ @domotorp Sorry, there should be exactly $k$ edges in the graph in my setting too; I've edited that into the post. So for $d=2$ these exactly correspond to permutations, and for general $d$ they will correspond to sets of $d-1$ permutations. $\endgroup$ – Benjamin Gunby Mar 15 '17 at 5:05

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.

  • 1
    $\begingroup$ All right, I'll try that, thanks! In fact I've seen attempts to do the generalization from the Klazar-Marcus proof, but I think the approach that works in the $d=2$ case fails (it works for $d$-regular hypergraphs that contain our $d$-permutation hypergraph, but fails for more general graphs). $\endgroup$ – Benjamin Gunby Mar 16 '17 at 23:31
  • 1
    $\begingroup$ It would be very interesting if their proof didn't work and ours would. I mean I always knew that they are quite different, but didn't expect them to be so different. $\endgroup$ – domotorp Mar 17 '17 at 4:34
  • 1
    $\begingroup$ I'm not convinced as to whether this generalizes directly... My main concern is that the step "if the number of $i$-wide blocks in an $i$-block column is at least $k$, then we can build a copy of $A$ from these blocks" doesn't quite carry over unless our graph is $d$-regular, because we don't know which elements of the hyperedge correspond to the vertices of $A$ (in particular, we don't know that the (size-$d$) edges of $A$ will always map to the first $d$ elements of a hyperedge). Am I missing something? $\endgroup$ – Benjamin Gunby Mar 18 '17 at 0:36
  • 1
    $\begingroup$ @Benjamin I've added some more details. $\endgroup$ – domotorp Mar 18 '17 at 7:58
  • 2
    $\begingroup$ @Benjamin You're right, this is more complicated than I've first thought. I've added some (hopefully correct) details. Sorry that the proof is not so neatly written, but it turned out to be quite complex and I'm also discovering it only on the fly - maybe you'll manage to simplify it. $\endgroup$ – domotorp Mar 28 '17 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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