7
$\begingroup$

This question concerns the structure of a directed graph built on the cells of an arrangement of lines. My basic question is whether this graph has been studied before, perhaps in another guise. I also ask a specific question.


Let $\cal A$ be an arrangement of $n$ lines in $\mathbb{R}^2$, with no line vertical, and no two lines parallel. I associate to $\cal A$ a directed graph $G$, with each node a cell of $\cal A$, and $a \to b$ iff cell $a$ is adjacently above $b$ in the sense that (1) $a$ and $b$ share an edge $e$, and (2) for a point $p$ in the interior of $e$, points vertically just below $p$ lie in $b$, and points vertically just above $p$ lie in $a$. Thus $e$ is an upper edge of $b$ and a lower edge of $a$.

Let $L^+$ be the line of $\cal A$ with the largest positive slope, and $L^-$ the line with the steepest negative slope. (From the assumptions, $L^+$ and $L^-$ are unique and distinct.) Then there is a unique unbounded cell $A$ of $\cal A$ that is bounded by $L^+$ and $L^-$ and has no cell adjacently above it, and similarly there is a unique unbounded cell $B$, also bounded by $L^+$ and $L^-$, which has no cell adjacently below. So $A$ is the unique source of $G$, and $B$ the unique sink.

Now I assign numbers/weights to the nodes of $G$ as follows. $A$ is assigned $1$. For any node $x$ of $G$, $x$ is assigned the sum of the weights of the nodes adjacently above $x$, i.e., with incoming arcs to $x$. Every node but $A$ has at least one incoming arc, and so this is well-defined.

Two $4$-line arrangements are shown below.


          Arr4
          $L^+$ and $L^-$ are colored green.
Every node but $B$ has at least one outgoing arc, so the weight of a node is always propagated downward. Thus the sink node $B$ receives the highest weight. In (a), $B$ has weight $8$, whereas in $B$ it has weight $9$.

A basic question is:

Q1. What is the largest possible weight assigned to the sink node $B$, over all arrangements of $n$ lines?

Here is a more complicated arrangement of $8$ lines, whose sink node has weight $111$.


          Arr8
(This was calculated by hand, so apologies if there are errors. Thanks to Will Brian for catching one error.)

The more general question is:

Q2. Has this graph and node-weighting scheme been studied before, perhaps in another context?

$\endgroup$
  • $\begingroup$ If you turn your page upside down, the sinkweights of your four-line graphs are $8$ and $7$ instead of $8$ and $9$. In either case, the sum (normal plus upside-down) is $16$. Checking a few cases, you can show that for $\leq 3$ lines the sum of the normal and upside-down sinkweights is always $2^n$. This also holds for one $5$-line case I worked out, the sum being $32$. (Though I have not checked this for your $8$-line case). This suggests that the sum (normal)+(upside-down) $= 2^n$. If so, the answer to your Q1 is always between $2^{n-1}$ and $2^n$ (and likely close to the former). $\endgroup$ – Will Brian Sep 17 '15 at 17:28
  • $\begingroup$ But I have no idea how to prove it. Also, I think there is an error in your $8$-line graph at the node with weight $16$ (and those below it). $\endgroup$ – Will Brian Sep 17 '15 at 17:29
  • $\begingroup$ @WillBrian. Thanks for the correction. And your $2^n$ hypothesis is brilliant! Perhaps it is connected to the similarity with Pascal's triangle... $\endgroup$ – Joseph O'Rourke Sep 17 '15 at 18:38
  • $\begingroup$ I think the upside-down sum idea doesn't quite work out (either that or my arithmetic is bad). I just tried your $8$-line configuration, and got $111$ for both sinkweights, for a sum of $222 \neq 256$. I did, however, find a way to prove that $2^{n-1}$ is a lower bound for Q1 (essentially by mimicking Pascal's triangle). I may post my lower bound as an answer later this afternoon if I can't figure out how to get a good upper bound. $\endgroup$ – Will Brian Sep 17 '15 at 19:39
  • 3
    $\begingroup$ The number at $B$ is simply the number of downward paths from $A$ to $B$ (actually, the number at any node is found in a similar way). So turning upside-down does not change the resulting number. $\endgroup$ – Ilya Bogdanov Sep 18 '15 at 10:05
2
$\begingroup$

We can always achieve exactly $2^{n-1}$ for the weight of the sink. This gives us a lower bound for the answer to Q1.

Essentially, the idea is that we draw our $n$ lines all tangent to the upper half of a circle. We then obtain a weight pattern identical to the first $n$ rows of Pascal's triangle, and the weight of the sink is gotten by adding together all the entries in the bottom row. I'm giving only a crude explanation, because a picture explains it much better. Here is $n = 5$ (the circle is shown in gray, and the faded red lines are showing you the rows of Pascal's triangle):

enter image description here

$\endgroup$
  • $\begingroup$ Very nice to use tangents to a circle! $\endgroup$ – Joseph O'Rourke Sep 17 '15 at 22:30

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.