Ruzsa–Szemerédi problem for regular graphs

Question

The Ruzsa–Szemerédi problem asks for the maximum number of edges in a locally linear graph, i. e. a graph in which every edge belongs to a unique triangle (equivalently, any two adjacent vertices have exactly one common neighbor). I am trying to solve the regular version of this problem: for a given $n$, what is the maximum number $r$ such that an $n$-vertex $r$-regular locally linear graph exists (let us denote this number as $r_n$)? This question seems quite natural and easier than the original one, though I couldn't find any publications on it. I'd be grateful for your proof tips or links.

Some trivial results I've found

1. $r_n$ is even.
2. $r_n$ or $n$ is divisible by $3$.
3. $r_n\leq n/3+1$
4. $r_n\leq\sqrt{2(n-1)}$ if there is an $n$-vertex $r_n$-regular locally linear graph containing no subgraphs isomorphic to the following graph:

Answer 1

I think I have a better solution than original. I really hope I did not make mistake.

Let $|G| = 3^k$

I would conjecture that $2^k\leq r_{3^k}$. Following is my attempt on the proof of that statement.

We will denote vertices of that graph with string of k digits between 0-2
We will denote a $rule$ as string of k digits between 0-2 with at least one non zero value
The action of a rule on a vertex or a rule will be result of adding digits on a respective positions modulo 3.

Example: $r = 011, v=121$
$r \circ v=102,r^2 \circ v= 110,r^3 \circ v = 121$

The rule will be a way in which we are constructing triangles. So looking in previous example vertices 121,102 and 110 would have all edges between them. But the choice of vertex is arbitrary so to obtain full set of edges we will apply all rules to all vertices.

Let $R_k$ be a set of rules length $k$ satisfying following conditions:

1. $\forall_{i,j}\; r_i^{p_1}\neq r_j^{p_2}$ where $p_1,p_2 \in \{1,2\}$
   
2. $\forall_{i,j,m}\; r_i^{p_1}\circ r_j^{p_2} \neq r_m^{p_2}$ where $p_1,p_2,p_3 \in \{1,2\}$
   

The first condition ensures two rules does not create the same triangle. The second one ensures that two adjacent vertices have exactly one common neighbor. As you might notice we can combine there two condition into one but I chose this way as it better illustrates the point.

T: Graph obtained from applying rules $R_k$ does not contain contain an edge belonging to two different triangles.

We can see there are two options for forming such an edge. Either that edge is contained in at least two triangles formed by our rules, or it is contained in a triangle formed by a different rules where it so happens they share vertices.

1. Lets assume there is an edge e=xy that can be obtained by applying two diffrent rules $r_1,r_2$. There are two cases to consider either $r_1\circ x = y\; \land \; r_2\circ x=y$ which is contradiction with condition 1.
   Or $r_1\circ x = y\; \land \; r_2\circ y=x$. In this case however observe that: $r_1^3\circ x=x \iff r_1^2 \circ r_1\circ x = x \iff r_1^2\circ y = x$ which once again is contradiction with condition $1$.
2. There is a triangle where all edges are obtained by different rules $r_1,r_2,r_3$. However following similar logic as previously we can see that: $r_1^{p_1}\circ r_2^{p_2}=r_3^{p_3}$ for some values of $p_1,p_2,p_2 \in \{1,2\}$ depending on the way the rule is acting and whether we need to reverse it or not. That is however a contradition with condition $2$.
   

I guess there is also a third option where same rule applied to different vertices produces two overlapping triangles. But we can easily see that such a case would either produce two different results of applying a same rule to a vertex which is impossbile or $r^2 = r^1$ which is only possible for string of all zeros.

Crude drawing of triangle from 2.

We will denote $|r|$ as the number of ones contained in a string $r$

Take $R_k$ as the set of all distinct strings length k containing only 0 and 1 and $\forall_{r} |r|$ is odd number.

Example: $k=3,\; R={001,010,100,111}$
$k=4,\; R={0001,0010,0100,1000,0111,1011,1101,1110}$

T: Such a set satisfies condition 1 and 2
Observe that none of the rules have a mixed values in them. Thus a sequence containing both 1's and 2's is impossible to obtain by applying same rule to itself.

1. Take $r_1,r_2$ Applying rule to itself cannot change number of 1's. Which means we cannot transform $r_1$ to $r_2$ through repeated application. Rules with the same number of 1's differ on at least 1 position. Which means there is position i where $r_1$ has 0, and $r_2$ has 1. This also makes is impossible to transform $r_1$ to $r_2$ .

2. Let $r_1,r_2$ be our rules from the left hand side. Let's consider following three cases:

   • $r_1$ and $r_2$ are overlapping completely. Then we can obtain a mix of 1 and 2 or shorter sequence of 1's. Let $|r_1|=2l_1+1,\;|r_2|=2l_2 +1$. Then the shorter sequence will have exactly $|r_1|-|r_2|=2l_1+1-(2l_2+1)=2(l_1-l_2)$ which is even number and thus not a rule by our of choice of $R_k$.

   • $r_1$ and $r_2$ are non overlapping. Then we can only obtain either sequence of 1's, or a mixed sequence of 1's and 2's. The length of the sequence of 1's is the sum of lengths of $r_1$ and $r_2$. Sum of two odd numbers is even thus it cannot be a rule.

   • $r_1$ and $r_2$ are partly overlapping. This means there exists i,j,k such that
     $r_1$ has 0 on $i$ position, 1 on $j$ and 1 on $k$.
     $r_2$ has 1 on $i$ position, 1 on $j$, and 1 on $k$.
     Lets consider all possibilities (restricted just to ijk):
     $r_1= 011,\;\; r_2=110\;\; r_1\circ r_2 = 121\;\;r_1^2\circ r_2 = 102\;\; r_1\circ r_2^2 = 201\;\; r_1^2\circ r_2^2 = 212$
     In all cases the the resulting action is containing a mix of 1's and 2's and so is not a valid rule.

This proves that graph with edges described by this rules is in fact locally linear. As each action is adding a unique triangle to our graph and thus adding 2 edges to each vertex we can compute $r=2|R|$ Where $|R|= \binom{k}{1}+\binom{k}{3}+\binom{k}{5}... = 2^{k-1}$

T: $\forall_{x,y}\;\; d(x,y)\leq2$
Let $x,y$ be two vertices where $d(x,y)\geq 2$. We will show there there exists two rules $r_1,r_2$ such that $r_1\circ r_2 = x-y$. As the rules denote a way we added edges to the graph this will mean there exists path length 2 between these vertices.

Let $x-y = i_1i_2...i_4$. Let denote number of 1's in represantation be $o$, and number of 2's as $t$.

Observe that in $R_k$ we have all possible distinct sequences with odd number of 1's. As such we can always find sequence that matches non zero positions in $x-y$ as long as the total number positions we want to match is odd.

1. o and t are both odd. Then we can take a rules with $|r_1|=o,|r_2|=t$.
   $r_1\circ r_2^2 = x- y$.

2. o and t are both even. If $o=0$ then we take $|r_1| = o-1 + t, |r_2|= 1$
   Then $r_1^2\circ r_2^2 = x-y$
   $o\neq 0$ then we can take $|r_1| = o-1 + t, |r_2|= 1+t$. Where the rules overlap on 2's and do not overlap on 1's. Then $r_1\circ r_2 = x-y$

3. o is odd, t is even. Then we can take $|r_1|=o+t, |r_2|=o$. Then $r_1^2\circ r_2^2=x-y$

4. o is even, t is odd. Then we can take $|r_1|=o+t, |r_2|=t$ Then $r_1\circ r_2^2 = x-y$

I am leaving original answer as I don't know the etiquette for editing answers with better solutions. Please remove is appropriate.

Not exatly what you asked for but I came up with a sort of lower bound for r.

Let $n = 3^p \Rightarrow 2\log_3 n \le r$

This comes from following construction:

$p = 1$

Take a triangle. Let vertices of that triangle be: $\{1,2,3\}$ It is easy to see $r_1 = 2$. ($r_t$ being r of p=t case)

$p = 2$

Take three copies of p=1 case. Let $V_i ={i1,i2,i3}$ where i = 1,2,3

Add triangles of following structure: $ij$, $(i+1)j$, $(i+2)j$ for i,j in $\{1,2,3\}$ (Looping back to one when necessary) We have added one triangle to each vertex so $r_2 = r_1+2$

$p = k$

Take three copies of p = k-1 case. Let $V_i =\{ij_1j_2...j_{k-1}\}$ where $i = 1,2,3$ and $j_1j_2...j_{k-1}$ are vertex labels of resultant graph from $k-1$ case.

Add triangles of following structure: $ij_1j_2....j_{k-1},\; ij_1j_2...j_{k-1},\; ij_1j_2,...j_{k-1}$ for i,j in $\{1,2,3\}$. We have added one triangle to each vertex so $r_n = r_k-1+2$

In general we can see that $p = k \Rightarrow r = p*2$. Considering that $p = \log_3 n$ we get the previous assertion.

This is a crude drawing of this procedure for $p = 1,2,3$ (Only a single triangle shown for $p=3$ case.) (Also I drew lines instead of triangles in $p=2$ case as that is easier to visualize, please imagine the third edge being there.)

Notes:

I think this is the extent of what I am able to prove but I wanted to add couple observations that I consider interesting but have no real proof of.

A p=2 case has diameter equal to 2 so no additional edge can be added. That is not true for p>=3 case.

In fact there is quite large amount of triples of unconnected vertices such that distance between each pair is at least 3.

It seems to me that:

• For $p=3$ we can add 1 more triangle to each vertex. Such triangle would take form of $ijk,\, i(j+1)(k+1),\, i(j+2)(k+2)$. (Looping back to one when necessary)

Drawing of example triangle. (There is a lot of missing edges here. Please imagine the missing ones)

If correct that would bring the diameter of that graph to 2 so no additional edge could be added.

• For $p=4$ it seems like we can add 4-5 triangles to each vertex instead of just 1. Though I am quite certain I made a mistake here, here is another crude drawing.

(There is a lot of missing edges here. Please imagine the missing ones)

I do not have enough skill to properly formalize or prove the $p=4$ case much less extend it further. But the idea of getting the lower bound for $r_n$ seems to be a promising one, at least when n is a power of 3.

I think I will stop here for now. If I ever get back to it I will try to update the answer. Hope this helps somehow.

Answer 2

As a comment to the answer above. Here, OP uses the technique that can be generalised as follows. Given a finite abelian group X, take a $2m$-element subset $A=\{a_{1,1},a_{1,2},...,a_{m,1},a_{m,2}\}\subseteq X$ such that (with the additive notation):

1. $0\notin A$
2. $\forall(x\in A):-x\in A$
3. $\forall(i\in[m]):a_{i,1}-a_{i,2}\in A$
4. $\forall(i,j\in[m])\forall(r,s\in[2]):i\neq j\rightarrow a_{i,r}-a_{j,s}\notin A$

Consider the graph $G_{X,A}$ such that $V(G_{X,A})=X$ and $x,y\in X$ are adjacent iff there is an element $z\in A$ such that $x+z=y$. One may prove that $G_{X,A}$ is locally linear (furthermore, conditions 3, 4 are necessary for our graph to be locally linear). One may also prove that each element in $A$ has order $3$ (the abelian case is crucial here).

In the above example, OP chooses as $X$ the $k$-th power of the cyclic group of order $3$ (which gives an abelian group). Then we can take as $A$ all vectors in $X$ with their coordinates are all non-zero. Ordering $A$ such that $a_{i,1}=-a_{i,2}$, we see that $A$ satisfies 1-4. Of course, $|A|=2^k$ which gives $G_{X,A}$ is a $2^k$-regular locally linear graph and $r_{3^k}\geq2^k$.