On Chordal Bipartite Graphs

It was on the 11th of January that my studies took me to Hagen again. This time, participating in the seminar from home using Adobe Connect was not an option, so I booked a room and got on a train. Normally—when in a seminar at an intramural university, that is—there will be one or two presentations per session, and the seminar will last for several sessions. Since things are a bit different when participants are coming from all across Germany, and sometimes from abroad as well, and are in some cases working while studying part‑time, a seminar at the University of Hagen needs to be organized accordingly.

There would be only one session, on a Saturday, beginning in the morning and lasting until the evening, intermitted only by a lunch break, so there would be enough time for everyone's presentations, of which there would be nine (minus those which ended up not being given). Each of the presentations was required to be 50 minutes in length—significantly longer than the one I had given for the number theory proseminar in my second term—, and all of them were to be based on a chapter or chapters of a book on graph theory:

Golumbic, Martin C. Algorithmic graph theory and perfect graphs. Amsterdam Boston: Elsevier, 2004. Print.

I had never studied graph theory before. There is a course offered by the University of Hagen that apparently some of the other participants had taken, but to me, absorbing the chapter I was assigned required that I treat myself to a crash course in graph theory on my own beforehand so I would have the fundamentals necessary to understand the text. Formally, said course was not a requirement to get a spot in the seminar, and with a little extra time investment, it is absolutely possible and feasible to tackle a special topic in graph theory without prior knowledge—as seems to be the case with discrete mathematics in general, as I have read.

So, not much after learning some of the most basic notions on graphs, I was making a deep dive into lifting the concept of chordality into the domain of bipartite graphs, and how this relates to perfect elimination. Elimination is something that may be considered common knowledge in that many of the general population encounter Gaußian elimination at some point in their schooling—the algorithm by which an invertible matrix is transformed into its reduced row echelon form. If a pivot is understood to be the element for which, in one iteration of the algorithm, the row and column are to be cleared of all other non‑zero elements, then an elimination scheme is the sequence of pivots chosen when performing the elimination. An elimination scheme is perfect when at no point during the execution of the algorithm a zero element becomes a non‑zero element.

The practical interest in perfect elimination schemes, as far as I can see, comes from computation involving large matrices. There is a rather large gap in size between the matrices the student usually computes with using their brain and pen and paper, and the matrices that are used in real‑world numeric computations. The human feels comfortable performing calculations on $3\times 3$-matrices, and can handle $6\times 6$-matrices if they must. In applications, matrices that are one million by one million in size are nothing extraordinary, and therefore some consideration has to be given to representing those matrices in computer memory and performing efficient computations on them. One favourable kind of matrix is the sparse matrix, i.e. a matrix where the large part of elements are zero, for it may be represented by storing the position and value of each non‑zero element. Perfect elimination is therefore favourable, because it guarantees that no new non‑zero elements are introduced.

There is a bridge then between matrices on one side and graphs on the other, for when disregarding the numeric value of an element, and considering only whether or not is is non-zero, there is a simple way to represent a matrix as a graph (which has to be a directed graph if the matrix is not symmetric), and another, not less simple way to represent it as a bipartite graph. (If a graph $(V,E)$ is a set of vertices $V$ paired with a set of edges $E=\{(v_i,v_j)\ |\ v_i,\ v_j \in V\}$ that designate connections between the vertices, a bipartite graph is a graph where the vertices consist of two disjoint subsets, and connections are only between vertices of different subsets.) Let us say we have a $4\times 4$-matrix $A=(a_{ij})$. The bipartite graph $(A,B,E)$ is constructed by creating four vertices, one for each row, and assigning them to $A$, and another four vertices, one for each column, and assigning them to $B$. An edge between a vertex $v_i$ in $A$ and a vertex $v_j$ in $B$ exists if and only if $a_{ij}\neq 0$.

It can be shown then, as Golumbic does, that an acceptable pivot in an elimination scheme—i.e. a pivot for which elimination does not introduce new non‑zero elements—corresponds to an edge in a so constructed bipartite graph which has the property of being bisimplicial, something on which I shall not elaborate here. The natural question that arises when thinking about perfect elimination schemes is, when does one exist? Or, which properties of a bipartite graph representation of a matrix tell us that the graph is a perfect elimination bipartite graph (PEBG)? The result of the chapter in Golumbic that was the topic of my presentation was:

$$ \begin{align*} & G \text{ is a chordal bipartite graph. }\\ \Rightarrow\ & G \text{ is a perfect elimination bipartite graph.} \end{align*} $$

...for which it is necessary to know what chordal bipartite means. A chordal graph is a simple graph (i.e. undirected and containing no loops or multiple edges) where every cycle of length $\geq 4$ has a chord, i.e. an edge between two of the cycle's vertices that is not part of the cycle itself. In a chordal bipartite graph, the limit for the cycle length is raised by two, so that a graph is chordal bipartite if every cycle of length $\geq 6$ has a chord (and, of course, the graph is bipartite to begin with.) By this definition, a chordal bipartite graph does not have to be chordal.

For a first leap into graph theory, I have not had too bad a time. I had not used the chalkboard in a long time, so writing on it felt a little awkward at first, but it turned out to be the right choice of medium. (The choice was between the chalkboard, an overhead projector, beaming slides from the computer, and mixed-media.) It definitely pays to make a mock presentation, if only whispering to yourself while sitting in bed, imagining the questions someone might be asking. For, contrary to expectations, the difficulty was not in producing enough text to fill the time allotted, but in cramming everything into those fifty minutes, and there were parts that I had prepared (proof details etc.) and had to skip because time was running out. In that sense, tempus fugit, and on with it!