# Above/below directed graph on cells of arrangement of lines

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.

$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$.

(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?

• 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). – Will Brian Sep 17 '15 at 17:28
• 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). – Will Brian Sep 17 '15 at 17:29
• @WillBrian. Thanks for the correction. And your $2^n$ hypothesis is brilliant! Perhaps it is connected to the similarity with Pascal's triangle... – Joseph O'Rourke Sep 17 '15 at 18:38
• 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. – Will Brian Sep 17 '15 at 19:39
• 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. – Ilya Bogdanov Sep 18 '15 at 10:05

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):