4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time $n^{4/3}$

Every vertex of $G$ is the concatenation of a possibly empty tuple of vectors of $S$, called vector tuple, followed by a possibly empty tuple of possibly equal indices of $[\ell]$, called index tuple. Each coordinate of the vector tuple is called a vector field, while each coordinate of the index tuple is called an index field. The set $V(G)$ is partitioned into four sets: $T$ (for triples), $C$ (for couples), $P$ (for pairs), and $I$ (for indices). The names behind $T,C,P$ reflect the number and the nature (ordered or unordered) of the vector fields. Each of these sets comprise vertices with up to three vector fields and five index fields. They are defined in the following way.

• •

  $T$: for every $\{a,b,c\}\in{S\choose 3}$, we add vertex $(a,b,c)$ to $T$. Thus vertices of $T$ have three vector fields and no index field.

• •

  $C$: for every $\{a,b\}\in{S\choose 2}$ and $i,j,k\in[\ell]$ such that $a[i]=a[j]=a[k]=1$ and $\text{maj}(b[i],b[j],b[k])=1$, we add vertex $(a,b,i,j,k)$ to $C$. Thus vertices of $C$ have two vector fields and three index fields.

• •

  $P$: for every $a,b\in S$ and $i,j,k\in[\ell]$ such that $a[i]=a[j]=a[k]=1$ and $b[i]=b[j]=b[k]=1$, we add vertex $(\{a,b\},i,j,k)$ to $P$. We will still see $a$ and $b$ as filling the two vector fields of the vertex, without a first vector field and a second vector field. Contrary to vertices of $C$, $(\{a,b\},i,j,k)$ and $(\{b,a\},i,j,k)$ are two names for the same vertex (whereas $(a,b,i,j,k)$ and $(b,a,i,j,k)$ are two distinct vertices, whose existence implies slightly different properties). Thus vertices of $P$ also have two vector fields and three index fields. Note also that $\{a,b\}$ is a multiset, since $a$ may be equal to $b$.

• •

  $I$: for every $p_{1},p_{2},i,j,k\in[\ell]$, we add vertex $(p_{1},p_{2},i,j,k)$ to $I$. The chosen labels for the five index fields anticipate that, to build the edge set, it is convenient to imagine a separation after the first two index fields of the tuple. The vertices of $I$ have no vector field and five index fields.

We will put some edges between $T$ and $C$, $C$ and $P$, $P$ and $I$, and $I$ and $T$. In addition, we put index-switching edges within $I$ and within $C$. An index-switching edge is between two vertices of the same set ($I$ or $C$) with the same vector tuple (which is always the case in $I$) and distinct index tuples. The only edges with a weight different than 1 are the edges between $I$ and $T$, which all have weight 3. Thus, unless specified otherwise, an edge has weight 1.

The total list of edges is as follows.

• •

  We add all the index-switching edges within $I$ and $C$. Thus $G[I]$ is a clique and $G[C]$ is a disjoint union of at most ${|S|\choose 2}$ cliques (while $G[T]$ and $G[P]$ remain independent sets). More explicitly, we have an edge between every pair of distinct vertices $(p_{1},p_{2},i,j,k)\in I$ and $(p^{\prime}_{1},p^{\prime}_{2},i^{\prime},j^{\prime},k^{\prime})\in I$, and for every $a\neq b\in S$ between every pair of distinct vertices $(a,b,i,j,k)\in C$ and $(a,b,i^{\prime},j^{\prime},k^{\prime})\in C$.

• •

  $E(T,C)$: We add an edge between every $(a,b,c)\in T$ and $(a,b,i,j,k)\in C$ provided that there is an $h\in\{i,j,k\}$ such that $b[h]=c[h]=1$.

• •

  $E(C,P)$: We add an edge between every $(a,b,i,j,k)\in C$ and $(\{c,d\},i,j,k)\in P$ whenever $a\in\{c,d\}$.

• •

  $E(T,I)$: We add an edge of weight 3 between every $(a,b,c)\in T$ and $(p_{1},p_{2},i,j,k)\in I$ whenever $a[p_{1}]=b[p_{1}]=c[p_{1}]=a[p_{2}]=b[p_{2}]=c[p_{2}]=1$.

• •

  $E(I,P)$: We add an edge between every $(p_{1},p_{2},i,j,k)\in I$ and $(\{a,b\},i,j,k)\in P$ whenever $a[p_{1}]=b[p_{2}]=1$ or $a[p_{2}]=b[p_{1}]=1$.

This ends the construction. See Figure 2 for an illustration.

There are $O(N^{3})$ vertices in $T$, $O(N^{2}\ell^{3})$, in $C\cup P$, and $\ell^{5}$, in $I$, hence $O(N^{3}+N^{2}\ell^{3}+\ell^{5})=O(N^{3})$ in total. There are $O(N^{3}\ell^{3})$ edges in $E(T,C)\cup E(C,P)$, $O(N^{2}\ell^{6})$, in $E(C)$, $O(N^{3}\ell^{5})$, in $E(T,I)$, $O(N^{2}\ell^{5})$, in $E(I,P)$, and $O(\ell^{10})$ in $E(I)$, hence $O(N^{3}\ell^{5}+N^{2}\ell^{6}+\ell^{10})=\tilde{O}(N^{3})$ edges in total. Furthermore $G$ can be built in time $\tilde{O}(N^{3})$.

As $G[I]$ is a clique and, by Lemma 3.1, $N^{3}[I]=V(G)$, every vertex $u\in I$ is at distance at most 4 from every vertex $v\in V(G)$.

For every $u\in P$, $N^{2}[u]\supset I$ and so $N^{4}[u]\supset P\cup C$, by Lemma 3.1. In particular there is a path of length at most 4 between $u$ and any vertex $v\in P\cup C$.

Let $(a,b)$ be the two vector fields of $u\in C$, $(c,d)$ be the first two vector fields of $v\in T\cup C$, and $e$ be the third vector field of $v$ if $v\in T$. Let $i=\text{ind}(a,b,c,d)$, $j=\text{ind}(a,c,d,e)$ if $v\in T$, and $j=i$ if $v\in C$. We observe that $(a,b,i,i,j),(\{a,c\},i,i,j),(c,d,i,i,j)$ are (existing) vertices of $C$, $P$, and $C$, respectively, and that $u-(a,b,i,i,j)-(\{a,c\},i,i,j)-(c,d,i,i,j)$ is a path of length 3 in $G$. The existence of these vertices is implied by $a[i]=b[i]=c[i]=d[i]=1$, $a[j]=c[j]=d[j]=1$. The first edge of the path is an index-switching edge within $C$. The existence of the other edges is implied by $a\in\{a,c\}$, $c\in\{a,c\}$, and the fact that the index tuple $(i,i,j)$ does not change.

Finally if $v\in C$, then the index-switching edge $(c,d,i,i,j)-v$ completes the $uv$-path of length 4. If instead $v\in T$, then the edge $(c,d,i,i,j)-(c,d,e)=v$ completes the $uv$-path of length 4. This edge exists since $d[j]=e[j]=1$.

Let $u=(a,b,c),v=(d,e,f)\in T$, $i=\text{ind}(a,b,c,d)$, $j=\text{ind}(a,b,d,e)$ and $k=\text{ind}(a,d,e,f)$. Then $u=(a,b,c)-(a,b,i,j,k)-(\{a,d\},i,j,k)-(d,e,i,j,k)-(d,e,f)=v$ is a path of length 4 in $G$. These vertices exist since $a$ and $d$ have value 1 on indices $i,j,k$, $b$, on indices $i,j$, and $e$, on indices $j,k$. The first edge exists since $b[i]=c[i]=1$, the next two edges exist for similar reasons as invoked in the previous paragraph, and the fourth edge exists since $e[k]=f[k]=1$.

Let $u=(a,b,c)\in T$ and $v=(\{d,e\},i,j,k)\in P$. We set $p_{1}=\text{ind}(a,b,c,d)$, $p_{2}=\text{ind}(a,b,c,e)$, and exhibit a $uv$-path of length 4 via $I$. Indeed $u=(a,b,c)-(p_{1},p_{2},i,j,k)-(\{d,e\},i,j,k)=v$ is a path of length 4 in $G$ (recall that the first edge of the path has weight 3). Edge $(a,b,c)-(p_{1},p_{2},i,j,k)\in E(T,I)$ exists since $a[p_{1}]=b[p_{1}]=c[p_{1}]=a[p_{2}]=b[p_{2}]=c[p_{2}]=1$. Edge $(p_{1},p_{2},i,j,k)-(\{d,e\},i,j,k)\in E(I,P)$ exists since $d[p_{1}]=e[p_{2}]=1$ and the three last indices $(i,j,k)$ remain unchanged.

As $\mathcal{P}$ cannot visit $I$ twice, if it visits $I$ then it has length exactly 6 and is one of the following kinds: (case 1) $T-I-T$, (case 2) $T-C-P-I-P-C-T$, or (case 3) $T-I-P-C-T$ (recall that the edges in $E(I,T)$ have weight 3). An important feature of such paths is that no index-switching edge can be used, thus the three last index fields (when they exist) have to remain the same.

Case 1. A path $(a,b,c)-(p_{1},p_{2},i,j,k)-(d,c,b)$ would in particular imply that $a[p_{1}]=b[p_{1}]=c[p_{1}]=d[p_{1}]=1$, contradicting the orthogonality of $a,b,c,d$.

Case 2. By 3.3 applied to both ends of the path, $\mathcal{P}$ is of the form $(a,b,c)-(a,b,i,j,k)-(\{a,e\},i,j,k)-(p_{1},p_{2},i,j,k)-(\{d,f\},i,j,k)-(d,c,i,j,k)-(d,c,b)$ with some $e,f\in S$. The existence of the vertices $(a,b,i,j,k),(d,c,i,j,k)\in C$ implies that $a[i]=a[j]=a[k]=d[i]=d[j]=d[k]=1$, and that $b$ and $c$ have value 1 on at least two indices (with multiplicity) of multiset $\{i,j,k\}$. In particular, there is an $h\in\{i,j,k\}$ such that $a[h]=b[h]=c[h]=d[h]=1$, a contradiction to $a,b,c,d$ being orthogonal.

Case 3. By 3.3 applied to the second half of the path, $\mathcal{P}$ has then the form $(a,b,c)-(p_{1},p_{2},i,j,k)-(\{d,e\},i,j,k)-(d,c,i,j,k)-(d,c,b)$. The first three vertices yield a contradiction. Indeed, the existence of edge $(p_{1},p_{2},i,j,k)-(\{d,e\},i,j,k)$ implies that $d[p_{z}]=1$ for some $z\in\{1,2\}$, while the existence of $(a,b,c)-(p_{1},p_{2},i,j,k)$ implies that $a[p_{z}]=b[p_{z}]=c[p_{z}]=1$.

We now consider paths $\mathcal{P}$ in $G[T\cup C\cup P]$. Since $a\neq d$, $\mathcal{P}$ has to visit $P$, since otherwise the first vector field cannot change, by 3.4. We then observe that no shortest $uv$-path visits $T$ a third time (one more time than the two endpoints $u$ and $v$). A $TT$-path visiting $T$ a third time would contain a segment $C-T-C$ that can be shortcut into $C-C$. Indeed, $(a,b,i,j,k)-(a,b,c)-(a,b,i^{\prime},j^{\prime},k^{\prime})$ has a chord $(a,b,i,j,k)-(a,b,i^{\prime},j^{\prime},k^{\prime})$ which is an index-switching edge of $C$.

We further distinguish two cases: (case 1) $\mathcal{P}$ does not contain any index-switching edge, or (case 2) $\mathcal{P}$ contains at least one index-switching edge.

Case 1. In that case, $\mathcal{P}$ is of the form $T-C-P-C-T$ or $T-C-P-C-P-C-T$. Either way, we consider the unique neighbors of $u$ and $v$ in $\mathcal{P}$. These neighbors have to be $(a,b,i,j,k)\in C$ and $(d,c,i,j,k)\in C$ for some $i,j,k\in[\ell]$. Indeed no index-switching edge nor return to $T$ is allowed here. Thus we conclude as in case A.2.

Case 2. We now assume that $\mathcal{P}$ contains at least one index-switching edge (of $C$). In that case, as $\mathcal{P}$ has length at most 6, it can visit $P$ only once. Hence $\mathcal{P}$ is of the kind $T-C-C-P-C-C-T$, where one of the two edges $C-C$ is optional. We consider the last vertex $u^{\prime}\in C$ before visiting $P$, and the first vertex $v^{\prime}\in C$ after visiting $P$. There is, by design, no index-switching edge between $u^{\prime}$ and $v^{\prime}$ on path $\mathcal{P}$. Thus by 3.4, there are $i,j,k\in[\ell]$ such that $u^{\prime}=(a,b,i,j,k)$ and $v^{\prime}=(d,c,i,j,k)$. We then conclude as in case A.2.

We add three sets to $V(G)$ to get $V(G^{\prime})$: two identical copies of $T$, denoted by $T^{\prime}$ and $T^{\prime\prime}$, and a set $I^{\prime}$ isomorphic to $[\ell]$. More precisely, for every $i\in[\ell]$, we add vertex $(i)$ to $I^{\prime}$. Thus $I^{\prime}$ has no vector field and a unique index field. We use a subscript to distinguish the homologous vertices in $T,T^{\prime},T^{\prime\prime}$. Vertices $(a,b,c)_{T}\in T,(a,b,c)_{T^{\prime}}\in T^{\prime},(a,b,c)_{T^{\prime\prime}}\in{T^{\prime\prime}}$ are the three vertices of $G^{\prime}$ corresponding to the same vertex $(a,b,c)$ of $G$.