2
$\begingroup$

I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $e_v$ denote the union of $\{v\}$ and the end vertices of edges starting at $v$. I would like to assure that there are sequences of vertices $\{v_i\}_{i=1}^j$ and $\{v'_i\}_{i=1}^j$ for a graph $G$ such that $v_{i+1}\in S_i\cap e_{v'_{i+1}}$ where $S_0=G$ and $S_{i+1}=S_i\setminus e_{v'_{i+1}}$ with $$j\geq \frac{kn}{d}-C$$ for a constant $C>0$ that does not depend on the graph $G$. The problem would be to show that we can create sequences long enough. The constant $C$ depend only on $d$ and $k$ while the length of the sequences $j$ can vary for different graphs of this type.

I am only able to prove this for $k(k+1)\leq d$, but I do not think this is optimal. It is easy to see that for $k=1$ it is possible to have inequality with $d=1$ and $C=1$. I would like to know if there are similar theorems already proven or any insight that might help prove or disprove this conjecture.

Improve this question
$\endgroup$
13
  • $\begingroup$ Did you type it correctly? Your displayed inequality has $j$ but the requirements don't have $j$. And what does $\{v_n\}_j$ mean; i.e. why is $n$ in this notation? $\endgroup$
    – Brendan McKay
    Commented Jan 30, 2023 at 8:26
  • $\begingroup$ I am sorry. I hope now it is clear enough :) $\endgroup$
    – Arturo
    Commented Jan 30, 2023 at 11:30
  • $\begingroup$ I'm still unsure. For $v_{i+1}$ to exist, $S_i\cap e_{v'_{i+1}}\ne\emptyset$, which means that $S_{i+1}$ is a proper subset of $S_i$ and so the maximum possible length is $n$. But you say you can prove it for $d\le k$, which includes cases where $kn/d-C>n$ for any $C=C(k,d)$. $\endgroup$
    – Brendan McKay
    Commented Jan 30, 2023 at 12:24
  • $\begingroup$ I do not know why I wrote that. My proof is for $k(k+1)\leq d$. It is not very illuminating: $e_v$ has $k+1$ elements so in the worst case $S_j$ will have $n-j(k+1)$ elements. Thus the minimum possible $j$ will be the integer part of $n/(k+1)$. $\endgroup$
    – Arturo
    Commented Jan 30, 2023 at 13:04
  • $\begingroup$ I do not understand what do you mean by the maximum possible length is $n$. That it is always to possible to have a sequence with $n$ elements or that the maximum length is at most $n$ although it might not reach $n$? $\endgroup$
    – Arturo
    Commented Jan 30, 2023 at 13:08

1 Answer 1

Reset to default
1
$\begingroup$

Let $q$ be a prime power and let $P$ be a projective plane of order $q$. It has $q^2+q+1$ points and $q^2+q+1$ lines. Each point lies on $q+1$ lines, and each line has $q+1$ points. Each pair of lines has exactly 1 common point. Since the point-line incidence graph is regular and bipartite, there is a bijection $L$ from points to lines such that $L(v)$ is a line through $v$ for every point $v$.

Now construct a graph $G$. The vertex set $V$ is the set of points of $P$. The out-neighbourhood of a vertex $v$ is $L(v)-v$, i.e. $e_v=L(v)$. So $n=q^2+q+1$ and $k=q$.

Now consider distinct $v'_1,\ldots,v'_{q+1}$. Since distinct lines have one common point, $|L(v'_1)\cup\cdots\cup L(v'_t)|\ge \sum_{i=1}^{q+1} (q-i+2)=\frac12(q+2)(q+3)>\frac12n+2q$. Thus, after $q+1=O(n^{1/2})$ steps, already less than half the vertices are available for the $\{v_i\}$ sequence. Even if all the remaining vertices can be chosen (most unlikely), in total less than half the vertices can be chosen.

I suspect the last part of this argument is unnecessarily weak and that the real bound is a lot smaller than $n/2$.

This example doesn't strictly violate the conjecture as stated since $C$ is allowed to be a function of $(k,d)$ which is a function of $n$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for the example! Another problem would be that there are parallel edges in the graph and that would also lead to $e_v$ with more elements. I think this could be avoided using another copy of $P$ and connecting one vertex $v$ to $L(v)$ in the other plane, but then the reasoning would not work. Also maybe you wanted to write $k=q$ instead of $d=q$. It would serve as a counterexample in both cases anyway (moving d or fixed d). $\endgroup$
    – Arturo
    Commented Jan 31, 2023 at 17:17
  • $\begingroup$ Yes, I meant to write $k=q$; fixed. There are no parallel edges. This is obvious for two edges $v\to w, v\to w$. If you want to exclude 2-cycles, like $v\to w, w\to v$ there are none of those either. $v\to w$ means that $w\in L(v)$, but then $v\notin L(w)$ since $L$ is a bijection and there is only one line through each pair of points. $\endgroup$
    – Brendan McKay
    Commented Feb 1, 2023 at 0:32
  • $\begingroup$ Incidentally, "parallel edges" in a digraph usually means two edges with the same start and the same end. It doesn't apply if they are oppositely oriented and if that's what you meant in your question you should clarify it. $\endgroup$
    – Brendan McKay
    Commented Feb 1, 2023 at 10:40
  • $\begingroup$ Indeed, I thought that discarded both cases, thanks! $\endgroup$
    – Arturo
    Commented Feb 1, 2023 at 16:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .