Distributional Graph Edge Coloring

We deal with directed graphs throughout this section, where self-loops are allowed and nodes are labeled. For simplicity, we simply use graphs to denote such directed graphs. Graphs are sampled by first selecting the number of nodes at random with respect to the default uniform distribution, then selecting a graph of nodes at random with uniform distribution (i.e., all graphs of nodes have the same probability).

For convenience, we will consider the distributional tiling problem in which corners (instead of edges) of tiles are marked with letters.

Venkatesan and Levin [VL88] constructed a randomized reduction from the distributional tiling problem to the distributional graph edge coloring problem. The proof presented here contains a number of modifications, and we provide all the details to make the proof accessible. Some of these details are extracted from [Ven91].

Let be a graph. We also use to denote the set of nodes in . Denote by the expected value of the random variable . Write if . If the symbols or are used without a variable, then we mean that the relation holds as . Let the graph be chosen at random. A property of is satisfied almost everywhere (or for almost every (a.e.) graph) if occurs in with probability .

The following two lemmas on probabilities and approximations are useful tools in studying random graphs. Their proofs are standard and can be found from numerous sources such as [Bol85].

Certain graph structures are needed for constructing the reduction. We will show that such structures exist on polynomial fraction of graphs. We first consider transitive tournaments, where a transitive tournament (or simply tournament) is an acyclic (expcept for self-loops at each node) complete digraph.

Proof. be the set of all -node subgraphs and for , let if is a tournament and 0 otherwise. Then . Let be the random variable for the number of pairs of -node tournaments sharing nodes. Then . To calculate , we first calculate the number of possible pairs of -node tournaments from -node graphs that share nodes. It is easy to see that for labeled nodes there are exactly tournaments. So the number of possible pairs is

Since for each pair of nodes, there are four possible ways to form an edge (including the empty edge), the probability of each pair is

It follows that . Note that . Using Stirling's approximation, we get

Hence,

Putting , we get and .

Denote by the expression (6.6) above. Then . We will show that for , either or .

It follows from (6.6) that . Note that . So for sufficiently large , we get

It follows from (6.7) that in the interval , decreases monotonically starting from and that . Similarly from (6.8), increases monotonically and reaches the maximum value at and so . This implies that . Let . When , using (6.4) and (6.6), we get

Thus,

Proof.first statement follows from . This bounds the size of the largest tournament. To see the second statement, note that implies , and so a -node tournament exists in almost every graph. The probability that a node extends a given -node tournament into a -node tournament is . Thus, the probability of a graph with a unique largest -node tournament is .

The following lemma is used to, on a given tournament, generate a random graph such that the given tournament is the largest and unique. Note that a complete directed graph (and so a tournament) always contains a Hamiltonian path that can be found in time polynomial of the number of nodes (see, for example, [Liu68]).

Proof.Corollary 6.7 (1), no -node tournaments exist on in almost every graph . However, an -node tournament disjoint with may share nodes and form a -node tournament. We are to show that the expected number of such tournaments is . Note that is the same as in Lemma 6.6 except that the nodes and edges of the -node tournament on are fixed here. Hence, by (6.2) and Stirling's approximation,

Summing over all possible values of , the result follows.

A degree of a node is the number of (incoming and outgoing) edges connecting to the node. Write for maximal degree of nodes in . An embedding is a one-one homomorphism. Note that in our sampling model, edges are chosen independently.

Proof. into independent sets , , where , such that . Split into disjoint sets , . Initially, let for all . Repeat the following step until is extended as required.

Extension step. Let be the nodes on which is defined (i.e., embedding has been found). Call a candidate for if letting would extend as an embedding over . For this, must satisfy at most many connectivity constraints. Consider the bipartite graph formed by connecting every node in to all of its candidates in . This graph has the edge probability , and by the condition on , a.e. such bipartite graph has a perfect matching (see [Bol85]). This matching finds a node satisfying the connectivity requirements for every node in and extends over .

The extensions are independent as are disjoint and the failure probability of each extension is exponentially small.

Write if there is an outgoing edge from to . Let be a Hamiltonian path of a tournament , where . The code of a node is a binary string of length in the form , where if and 0 otherwise [BES80]. The code of with respect to is the restriction of its code to the digits and .

A looped node is called blank if its self-loop is not colored.

Proof.fix a reduction from to the distributional tiling problem. Let () be an instance of the distributional tiling problem produced by the reduction, where is a set of constant number of tiles with marked corners. We distinguish the tiles by coloring the corners of the tiles. Without loss of generality, we assume that the following particular tiles are included. Namely, the lower left corner is colored blank, which represents the initial state of a universal Turing machine with the head looking at the right, and other three corners are colored with non-blank colors (one such tile encodes the case when the first bit of the input to the universal Turing machine is 0, and the other encodes the case when the first bit of the input is 1). Note that tiles cannot be rotated or turned over. Any other tiles will have all their corners colored by non-blank colors. The first tile in has a blank lower left corner, and encodes the input of (for example, if the th digit of the input is 1, then the lower right corner of the th tile of is marked with 1). Clearly, The number of colors depends only on a fixed universal Turing machine that accepts , and so is a constant. We may use a small universal Turing machine (in terms of the number of states and symbols) to reduce the number of colors. Small universal Turing machines have been studied in [Pre79][Min67][Wat61][Ike58][Sha56] and other literature.

Let

Note that for some . Hence, , which implies that .

We partition at random into disjoint sets

such that

and

Let and .

We then randomly order as and extend it by randomly adding edges into a graph of nodes. The graph is random except that the following properties are enforced.

P1

forms a tournament and forms a Hamiltonian path. (It can be shown that is the largest and unique tournament in a polynomial fraction of graphs, which will be used to enforce the graph structures and the color pattern.)

P2

is the set of all nodes with self-loops.

P3

Every node in is connected to every node in .

Arrange the nodes in in the decreasing order of codes as and connect to . Then add or delete the edges between successive input nodes to encode : the edge encodes 0 (meaning that the th bit of the input is 0), the edge encodes 1 (meaning that the th bit of the input is 1), and the absent of edge between and means there is no input on position . The nodes in are called input nodes. The resulted graph is the desired graph .

Proof.show that a random graph of nodes has the required distribution. The probabilities mentioned below in p1, p2, and p3 are the probabilities of satisfying P1, P2, and P3, respectively.

p1

Note that . It follows from Corollary 6.7 (2) that a -node random graph has a unique largest -node tournament with probability . So with probability at least a random has a -node tournament. By Corollary 6.8, a.e. has no -node tournament other than .

p2

A random has exactly looped nodes with probability

p3

Note that there are possible ways for each node not in to connect to every node in . Also, , where . So the probability of success is . Hence, the expected number of looped nodes in a graph satisfying P1 and P2 and connected to every node in is

It follows from Lemma 6.5 (3) that

We now deal with unlooped nodes. Similarly, we can show that the expected number of unlooped nodes in a graph satisfying P1 and P2 and connected to every node in is , and so

Thus, all these properties hold with probability

It is easy to see, from the above proof, that the number of random bits needed to generate is . Hence, we may consider random strings of length starting with zeros. The rest of the random bits are sufficient to generate a random graph with the desired structure. We will show (in Lemma 6.13 below) that for a.e. such random string , can be extended to tile an squre using tiles from iff is colorable under the given color specification and constraints (which will be described later). Let be the set of all such random strings . Then is a good-input domain. Let . Then . Since , is non-rare.

The desirable reduction (for ) is the graph we constructed above plus a color specification and a set of constraints that we will describe later. We first describe the structures we need for coloring. The essential part of the structures is restricted to the nodes in .

Structures

For convenience, we will use various types of links to classify edges. Links will be directional (i.e. asymmetric), Each type of links are associated with a symbolic name (written in bold face) and a direction. The reduction will contain information about these links. A link between and can be identified by inspecting the two-node spot (i.e. the induced edge with the induced color). Write to denote that is connected to by an -link. The following types of links will be used frequently: (for horizontal), (for vertical), (for diagonal), (for toroidal), (for input chain), and (for key). The meanings of these links will be given below when they are introduced.

If on a subset of nodes, exactly one outgoing and incoming links of the same class (for example, ) exist for every node, then that class naturally induces a permutation on this subset of nodes. We then write, for instance, and accordingly.

When a self-loop is colored, it is convenient to simply say that the looped node is colored (with the same color of the self-loop).

The Input Chain

Proof.is straightforward to show the following claim. Let integers be chosen uniformly and independently at random from , where . Then the probability that all these numbers are distinct is

A code word for a node in is a sequence of pairs of binary digits, where the -th pair of digits corresponds to the connection to the -th node in . Except for 00, all other three combinations are possible. So there are possible code words for a node in . By construction,

Take and in the above claim, then the lemma follows.

Recall that nodes in are called input nodes and there is an edge from to . Also, . Let . Thus, in a.e. , a monotonically decreasing codes of the input nodes as produces a unique sequence. This ordering can be illustrated as follows. For each , let be the length of the maximal joint prefix of the codes of and . The edge connecting and is called a -link. A -link connecting to corresponds to the th digit of its code.

Assign nodes to form a path: where for . We call this path an input chain. The edges on the path are called -links. There are exactly -links and exactly -links.
Toroidal Grids

A product of two graphs and is the graph such that and . A toroidal grid is a graph obtained by adding at most one of the diagonals to the smallest squares in the product of two directed cycles.

Consider a directed cycle of order , where each node has a self-loop. The product of by induces an toroidal grid pattern called a primary grid. Except for the edges induced from (called the toroidal edges), all edges in the same row point to the same direction, and so do the edges in the same column. Horizontal edges (including the horizontal toroidal edges) in the grid are called -links, and vertical edges (including the vertical toroidal edges) are called -links. (Some toroidal edges are neither horizontal nor vertical. We simply refer them as toroidal edges.) Clearly, and are identities. Let and , which define the diagonals in the smallest squares of the toroidal grid. It is easy to see that the toroidal grid guarantees the following connectivity: for any node on the grid, for some and .

We now consider a toroidal grid by arranging all the nodes in to pass through the entire primary grid such that the bottom row is, from left to right, , and the next row is , etc.

Hence, each looped node in has at most one link of each of the following types: -link, incoming and outgoing , , , , and links. Each unlooped node in has at most one incoming (respectively, outgoing) -link. has no incoming -link.

We note that in the input chain and the grid pattern we described above, all nodes except have a bounded degree. Let be a graph that contains , the toroidal grid , and the input chain as induced subgraph. Let in the Embedding Lemma. It is easy to extend to a graph of nodes such that all nodes in have a bounded degree, and so the condition of the Embedding Lemma is satisfied. Hence, the Embedding Lemma guarantees the existence of the desired structure (the input chain and the grid) in a.e. . The embedding is identical on and preserves all types of links. By the Embedding Lemma, the embedding can be found in polynomial time. Note that the embedding gives a permutation of the indexing for nodes in and we described above. So without loss of generality, we still assume the same indexing in the discussion below.
Coloring the Random Graph

The following edges are colored blank: all the -links, all the -links, all the -links, all the self-loops in , all the edges in the fixed Hamiltonian path of , all the -links, and all the -links. Let specify these as constraints.

The diagonals -links and -links are distinguished by two different colors. All other edges not specifically mentioned above are colored by a color that has not been used in coloring the tiles in .

The smallest squares in the toroidal grid can be viewed as tiles. The initial tiling sequence of is determined by the connectivity pattern of the chain as described before, which will be represented by coloring the looped nodes in the bottom row of the toroidal grid, exactly the same as the correspondent colors in .

If is a positive instance of the distributional tiling, then the tiling pattern can be mapped to the grid. So all the looped nodes in can be colored by embedding a tile in the smallest square of the grid iff is a positive instance. Clearly, the number of colors used to color the graph is a constant, which depends only on the fixed set of tiles .

On the toroidal grid , and , , are the toroidal edges and the edge is a double edge. So there are toroidal edges. There are and -links that are non-toroidal edges. On the input chain, there are -links and -links. On the tournament , there are self-loops and edges on the Hamiltonian path. Thus, the number of blank edges in a colored graph that exhibits the tiling pattern is equal to

The coloration is , where is the set of all possible spots induced from colored graphs that represent tiling patterns for positive instances . It is not difficult to describe these spots. For instance, includes all spots induced from colored tiles (by mapping a colored tile into one of the smallest square of the grid), but does not contain spots that contain a looped loop colored by the default color while all edges are colored blank. Clearly, if is a positive instance of the distributional tiling, then for a.e. produced by the randomized reduction , is colorable.

Next, we show that if can be colored, under the constrain , to obtain a coloration such that , then the coloration will enforce to be colored that represents a tiling pattern. This implies that is a positive instance of the distributional tiling. Moreover, the tiling pattern can be obtained easily from the coloring. To see this, we first note that the blank edges are exactly those specified in , which lay down the framework for simulating tiling. Note that is a unique triangle due to the selection of by decreasing code. Since has to be colored blank, this triangle enforces the beginning of the tiling simulation. Note that triangles will enforce the initial sequence , where the presence or absence of an edge between to depends on . Hence, is forced to be colored to represent an tiling pattern. This proves the following lemma.

The reduction we described above is clearly one-one and p-time computable since the embedding is one-one and p-time computable. Also, although may not be certifiable, a solution to the coloring can be transformed to a solution to the tiling by the reduction, and so the correctness of the yes/no answer to can be efficiently verified to perform the iteration (see Theorem 6.1).

We are only left to verify that the domination condition is satisfied. Note that the size of is proportional to , and so is proportional to . Hence, the probability of is proportional to . By definition, , where is the probability distribution of . Since and , when is sufficiently large. Also note that . Hence, is dominated by the distribution of . This completes the proof.