Relation to Median Graph and Whether a Graph Is Triangle-Free

A recently published opinion piece in The Times, called "Is Algebra Necessary?," generated much hubbub in education circles. Its premise -- that we should at least consider jettisoning algebra course requirements because many students who fail algebra eventually drop out of college -- was met with cries of derision. Yet`nary has a word been said about the continuing erosion of English instruction in our schools. Bit by bit, the body of English language instruction has been dismembered over the last 15 years or so. First to be lopped off was spelling. Other than in elementary schools, spelling tests are all but forgotten, apparently on the premise that word processors will do the trick. Then vocabulary was subjected to the ax. Gone are the vocabulary lists of old, to be replaced with Next to be hacked off was grammar, which must also be taught in context rather than systematically. Students don't know they’re there from their they're (I'll wager that no more than 1 in 10 students today can parse that sentence). Finally, creative writing has been chopped clean away, to be replaced with unending persuasive essays that are the darlings of the Common Core standards. Even reading has not been left unscathed. Many schools teach reading as a set of skills to be mastered rather than as a journey to be embarked upon. Children are taught how to predict, to connect, to draw inferences, and so forth, but they are rarely allowed the leisure to savor what they read or to reflect on the art of good writing. I personally felt the effects of the Common Core keenly last year. As part of our sixth grade curriculum in my school, we analyze novels in light of the Joseph Campbell's hero's journey in "The Hero with a Thousand Faces."

In mathematics, a binary operation on a set is a calculation that combines two elements of the set (called operands) to produce another element of the set (more formally, an operation whose arty is two, and whose two domains and one co domain are (subsets of) the same set). Examples include the familiar elementary arithmetic operations of addition, subtraction, multiplication and division. Other examples are readily found in different areas of mathematics, such as vector addition, matrix multiplication and conjugation in groups. More precisely, a binary operation on a set S is a map which sends elements of the Cartesian product S × S to S: Because the result of performing the operation on a pair of elements of S is again an element of S, the operation is called a closed binary operation on S (or sometimes expressed as having the property of closure). If f is not a function, but is instead a partial function, it is called a partial binary operation. For instance, division of real numbers is a partial binary operation, because one can't divide by zero: a/0 is not defined for any real a. Note however that both in algebra and model theory the binary operations considered are defined on all of S × S. Sometimes, especially in computer science, the term is used for any binary function. essential in the definitions of groups, monoids, semi groups, rings, and more. Most generally, a magma is a set together with some binary operation defined on it. Typical examples of binary operations are the addition (+) and multiplication (×) of numbers and matrices as well as composition of functions on a single set. For instance,

• On the set of real numbers R, f(a,b) = a + b is a binary operation since the sum of two real numbers is a real number.

• On the set of natural numbers N, f(a,b) = a + b is a binary operation since the sum of two natural numbers is a natural number. This is a different binary operation than the previous one since the sets are different.

• On the set M(2,2) of 2 × 2 matrices with real entries, f(A, B) = A + B is a binary operation since the sum of two such matrices is another 2 × 2 matrix.

• On the set M(2,2) of 2 × 2 matrices with real entries, f(A, B) = AB is a binary operation since the product of two such matrices is another 2 × 2 matrix.

• For a given set C, let S be the set of all functions h: C → C. On S, f(g,h) = g h = g(h(c)), the composition of the two functions g and h, is a binary operation since the composition of the two functions is another function on the set C (that is, a member of S).

Many binary operations of interest in both algebra and formal logic are commutative, satisfying f(a,b) = f(b,a) for all elements a and b in S, or associative, satisfying f(f(a,b), c) = f(a, f(b,c)) for all a, b and c in S. Many also have identity elements and inverse elements. The first three examples above are commutative and all of the above examples are associative. The paper-scissors-rock binary operation is commutative but not associative. On the set of real numbers R, subtraction, that is, f(a,b) = a - b, is a binary operation which is not commutative since, in general, a - b ≠ b - a. It is also not associative, since, in general, a - (b - c) ≠ (a - b) - c; for instance, 1 - (2 - 3) = 2 but (1 - 2) - 3 = -4. On the set of natural numbers N, the binary operation exponentiation, f(a,b) = ab, is not commutative since, in general, ab ≠ ba and is also not associative since f(f(a,b),c) ≠ f(a, f(b,c)). For instance, with a = 2, b = 3 and c = 2, f(23,2) = f(8,2) = 64, but f(2,32) = f(2,9) = 512. By changing the set N to the set of integers Z, this binary operation becomes a partial binary operation since it is now undefined when a = 0 and b

in the set, which is not an identity (two sided identity) since f(1, b) ≠ b in general. Division (/), a partial binary operation on the set of real or rational numbers, is not commutative or associative as well. Tetration(↑↑), as a binary operation on the natural numbers, is not commutative nor associative and has no identity element. Binary operations are often written using infix notation such as a*b, a + b, a·b or (by juxtaposition with no symbol) ab rather than by functional notation of the form f(a, b). Powers are usually also written without operator, but with the second argument as superscript. Binary operations sometimes use prefix or (probably more often) postfix notation, both of which dispense with parentheses. They are also called, respectively, Polish notation and reverse Polish notation. A binary operation, ab, depends on the ordered pair (a, b) and so (ab)c (where the parentheses here mean first operate on the ordered pair (a, b) and then operate on the result of that using the ordered pair ((ab), c)) depends in general on the ordered pair ((a, b), c). Thus, for the general, non-associative case, binary operations can be represented with binary trees. However:

• If the operation is associative, (ab)c = a(bc), then the value of (ab)c depends only on the tuple (a, b, c).

• If the operation is commutative, ab = ba, then the value of (ab)c depends only on { {a, b}, c}, where braces indicate multisets.

• If the operation is both associative and commutative then the value of (ab)c depends only on the multiset {a, b, c}.

• If the operation is associative, commutative and idempotent, aa = a, then the value of (ab)c depends only on the set {a, b, c}.

• In mathematics, a ternary operation is an n-ary operation with n = 3. A ternary operation on a set A takes any given three elements of A and combines them to form a single element of A. An example of a ternary operation is the product in a heap.

• In computer science, a ternary operator (sometimes incorrectly called a tertiary operator) is an operator that takes three arguments. The arguments and result can be of different types. Many

expression. Since this operator is often the only existing ternary operator in the language, it is sometimes simply referred to as "the ternary operator". In some languages, this operator is referred to as "the conditional operator". In mathematics, a median algebra is a set with a ternary operation satisfying a set of axioms which generalise the notion of median or majority function, as a Boolean function. The axioms are 1. 2. 3. 4. The second and third axioms imply commutatively: it is possible (but not easy) to show that in the presence of the other three, axiom (3) is redundant. The fourth axiom implies associativity. There are other possible axiom systems: for example the two

also suffice. In a Boolean algebra, or more generally a distributive lattice, the median function satisfies these axioms, so that every Boolean algebra and every distributive lattice forms a median algebra. Birkhoff and Kiss showed that a median algebra with elements 0 and 1 satisfying < 0,x,1 > = x is a distributive lattice.

A median graph is an undirected graph in which for every three vertices x, y, and z there is a unique vertex < x,y,z > that belongs to shortest paths between any two of x, y, and z. If this is the case, then the operation < x,y,z > defines a median algebra having the vertices of the graph as its elements. x,y,z > = y. One may define a graph from a median algebra by creating a vertex for each algebra element and an edge for each pair (x, z) such that the interval [x, z] contains no other elements. If the algebra has the property that every interval is finite, then this graph is a median graph, and it accurately represents the algebra in that the median operation defined by shortest paths on the graph coincides with the algebra's original median operation. In mathematics, and more specifically graph theory, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c. The median of three vertices in a tree, showing the subtree formed by the union of shortest paths between the vertices. Every tree is a median graph. To see this, observe that in a tree, the union of the three shortest paths between pairs of the three vertices a, b, and c is either itself a path, or a subtree formed by three paths meeting at a single central node with degree three. If the union of the three paths is itself a path, the median m(a,b,c) is equal to one of a, b, or c, whichever of these three vertices is between the other two in the path. If the subtree formed by the union of the three paths is not a path, the median of the three vertices is the central degree-three node of the subtree. median m(a,b,c) can be found as the median of the coordinates of a, b, and c. Conversely, it turns out that, in every median graph, one may label the vertices by points in an integer lattice in such a way that medians can be calculated coordinatewise in this way. Squaregraphs, planar graphs in which all interior faces are quadrilaterals and all interior vertices have four or more incident edges, are another subclass of the median graphs. A polyomino is a special case of a squaregraph and therefore also forms a median graph. The simplex graph κ(G) of an arbitrary undirected graph G has a node for every clique (complete subgraph) of G; two nodes are linked by an edge if the corresponding cliques differ by one vertex. The median of a given triple of cliques may be formed by using the majority rule to determine which vertices of the cliques to include; the simplex graph is a median graph in which this rule determines the median of each triple of vertices. No cycle graph of length other than four can be a median graph, because every such cycle has three vertices a, b, and c such that the three shortest paths wrap all the way around the cycle without having a common intersection. For such a triple of vertices, there can be no median. The problems of testing whether a graph is a median graph, and whether a graph is triangle-free, both had been well studied when Imrich, Klavžar & Mulder (1999) observed that, in some sense, they are computationally equivalent. Therefore, the best known time bound for testing whether a graph is triangle-free, O(m1.41), applies as well to testing whether a graph is a median graph, and any improvement in median graph testing algorithms would also lead to an improvement in algorithms for detecting triangles in graphs. In one direction, suppose one is given as input a graph G, and must test whether G is triangle-free. From G, construct a new graph H having as vertices each set of zero, one, or two adjacent vertices of G. Two such sets are adjacent in H when they differ by exactly one vertex. An equivalent description of H is that it is formed by splitting each edge of G into a path of two edges, and adding a new vertex connected to all the original vertices of G. This graph H is by construction a partial cube, but it is a median graph only when G is triangle-free: if a, b, and c form a triangle in G, then {a,b}, {a,c}, and {b,c} have no median in H, for such a median would have to correspond to the set {a,b,c}, but sets of three or more vertices of G do not form vertices in H. Therefore, G is triangle-free if and only if H is a median graph. In the case that G is triangle-free, H is its simplex graph. An algorithm to test efficiently whether H is a median graph could by this construction also be used to test whether G is

of H is proportional to that of G. The reduction in the other direction, from triangle detection to median graph testing, is more involved and depends on the previous median graph recognition algorithm of Hagauer, Imrich & Klavžar (1999), which tests several necessary conditions for median graphs in near-linear time. The key new step involves using a breadth first search to partition the graph into levels according to their distances from some arbitrarily chosen root vertex, forming a graph in each level in which two vertices are adjacent if they share a common neighbor in the previous level, and searching for triangles in these graphs. The median of any such triangle must be a common neighbor of the three triangle vertices; if this common neighbor does not exist, the graph is not a median graph. If all triangles found in this way have medians, and the previous algorithm finds that the graph satisfies all the other conditions for being a median graph, then it must actually be a median graph. Note that this algorithm requires, not just the ability to test whether a triangle exists, but a list of all triangles in the level graph. In arbitrary graphs, listing all triangles sometimes requires Ω(m3/2) time, as some graphs have that many triangles, however Hagauer et al. show that the number of triangles arising in the level graphs of their reduction is near-linear, allowing the Alon et al. fast matrix multiplication based technique for finding triangles to be used.

A median graph is an undirected graph in which for every three vertices x, y, and z there is a unique vertex < x,y,z > that belongs to shortest paths between any two of x, y, and z. If this is the case, then the operation < x,y,z > defines a median algebra having the vertices of the graph as its elements. Conversely, in any median algebra, one may define an interval [x, z] to be the set of elements y such that < x,y,z > = y. One may define a graph from a median algebra by creating a vertex for each algebra element and an edge for each pair (x, z) such that the interval [x, z] contains no other elements. If the algebra has the property that every interval is finite, then this graph is a median graph, and it accurately represents the algebra in that the median operation defined by shortest paths on the graph coincides with the algebra's original median operation. In an arbitrary graph, for each two vertices a and b, the minimal number of edges between them is called their distance, denoted by d(x,y). The interval of vertices that lie on shortest paths between a and b is defined as A median graph is defined by the property that, for every three vertices a, b, and c, these intervals intersect in a single point: For all a, b, and c, |I(a,b) ∩ I(a,c) ∩ I(b,c)| = 1. Equivalently, for every three vertices a, b, and c one can find a vertex m(a,b,c) such that the unweighted distances in the graph satisfy the equalities

• d(a,b) = d(a,m(a,b,c)) + d(m(a,b,c),b)

• d(a,c) = d(a,m(a,b,c)) + d(m(a,b,c),c)

• d(b,c) = d(b,m(a,b,c)) + d(m(a,b,c),c)

and m(a,b,c) is the only vertex for which this is true. It is also possible to define median graphs as the solution sets of 2-satisfiability problems, as the retracts of hypercubes, as the graphs of finite median algebras, as the Buneman graphs of Helly split systems, and as the graphs of windex 2; see the sections below.

1. Buneman (1971); Dress et al. (1997); Dress, Huber & Moulton (1997). 2. Bandelt & Barthélémy (1984); Day & McMorris (2003). 3. Imrich & Klavžar (2000), Proposition 1.26, p. 24. 4. This follows immediately from the characterization of median graphs as retracts of hypercubes, described below. 5. Soltan, Zambitskii & Prisˇacaru (1973); Chepoi, Dragan & Vaxès (2002); Chepoi, Fanciullini & Vaxès (2004). 6. Birkhoff & Kiss (1947) credit the definition of this operation to Birkhoff, G. (1940), Lattice Theory, American Mathematical Society, p. 74. 7. Knuth (2008), p. 65, and exercises 75 and 76 on pp. 89–90. Knuth states that a simple proof that associativity implies distributivity remains unknown. 8. The equivalence between the two expressions in this equation, one in terms of the median operation and the other in terms of lattice 9. Birkhoff & Kiss (1947), Theorem 2. 10. Birkhoff & Kiss (1947), p. 751. 11. Avann (1961). 12. Knuth (2008) calls such a set an ideal, but a convex set in the graph of a distributive lattice is not the same thing as an ideal of the lattice. 13. Imrich & Klavžar (2000), Theorem 2.40, p. 77. 14. Bandelt & Chepoi (2008), Proposition 2.5, p.8; Chung, Graham & Saks (1989); Feder (1995); Knuth (2008), Theorem S, p. 72. 15. Hell (1976). 16. Imrich & Klavžar (2000), Proposition 1.33, p. 27. 17. Bandelt (1984); Imrich & Klavžar (2000), Theorem 2.39, p.76; Knuth (2008), p. 74. 18. The technique, which culminates in Lemma 7.10 on p.218 of Imrich and Klavžar, consists of applying an algorithm of Chiba & Nishizeki (1985) to list all 4-cycles in the graph G, forming an undirected graph having as its vertices the edges of G and having as its edges the opposite sides of a 4-cycle, and using the connected components of this derived graph to form hypercube coordinates. An equivalent algorithm is Knuth (2008), Algorithm H, p. 69. 19. For previous median graph recognition algorithms, see Jha & Slutzki (1992), Imrich & Klavžar (1998), and Hagauer, Imrich & Klavžar (1999). For triangle detection algorithms, see Itai & Rodeh (1978), Chiba & Nishizeki (1985), and Alon, Yuster & Zwick (1995). 20. Alon, Yuster & Zwick (1995), based on fast matrix multiplication. Here m is the number of edges in the graph, and the big O notation hides a large constant factor; the best practical algorithms for triangle detection take time O(m3/2). For median graph recognition, the time bound can be expressed either in terms of m or n (the number of vertices), as m = O(n log n). 21. Mulder & Schrijver (1979) described a version of this method for systems of characteristics not requiring any latent vertices, and Barthélémy (1989) gives the full construction. The Buneman graph name is given in Dress et al. (1997) and Dress, Huber & Moulton (1997). 22. Mulder & Schrijver (1979). 24. Mulder (1980).