Abstract:
A recurring theme in the study of various combinatorial structures and their applications is looking at the frequencies of small substructures occurring in them. A classical example of such a quantity is #H, the number of copies of H that occur as an induced subgraph in the random graph G(n,p), where each two of the n vertices are connected by an edge independently with probability p. It was discovered by Janson (1995) that the distribution of #H in G(n,p) has variance Θ(n^(2|H|-2)) and coverages to a normal distribution under proper normalization, apart from some special degenerate cases. In these degenerate cases, all subgraphs of size three occur in H exactly in proportion to their average frequencies in G(n, p). The question of existence of such proportional graphs is nontrivial. Janson and Spencer (1992) showed that proportional graphs exist for any rational p and all sufficiently large n satisfying some modulo conditions.
In this talk, We extend the notion of proportionality to edge-colorings of the complete graph with any number of colors, rather than two. We give a probabilistic construction of proportional edge-colorings with respect to random models where every edge is independently assigned a random color according to some rational probability vector, extending the result on graphs by Janson and Spencer. The extension both contains new ideas related to many colors, and provides new elements streamlining the existing r=2 proof. The idea of this construction is algorithmic, and we find an explicit minimal example of an 81-vertex proportional 3-coloring via a computer search which follows a similar approach.
MSc seminar; Advisor: Chaim Even-Zohar
