CSC 482/582: Fall 2016 Assignment #3
Due at the beginning of class, Tues. Nov. 8, 2016

Instructions for all assignments:

  1. Draw boxes for your marks on the top of the first page of your submission. Place a 0 in the corresponding box for any questions you omit. For this assignment:
    Question12345
    Marks 0 0 0 0 0
  2. Questions must be submitted in order.
  3. Written submissions can be handed in up to 4 days late with a 10% penalty for each day past the deadline. If you want to submit your written work on a day that we do not have class, please write the day and time submitted on your first page and slip it under my office door (ECS 552).
  1. [20 marks] Prove that this Venn diagram is extendible to a simple 6-Venn diagram by showing one way to add another curve to obtain a 6-Venn diagram:

    This picture was extracted from a talk given by Frank Ruskey. Side note: "simple" was added as a constraint after the initial assignment was posted. If you can find a simple one it would be better preparation for the projects. But since I added the constraint late, you can get marks for not simple.

  2. Consider 3-regular polyhedra whose face sizes are 4, or 7.
    (a) [5 marks] List all the possible vertex types and determine the curvature for each as a rational number.
    (b) [5 marks] Which vertex types have strictly positive curvature?
    (c) [5 marks] Give the integer programming problem for trying to find a maximum n for a 3-regular PCC-polyhedron with face sizes 4, and 7 that has these constraints:
    Maximize n subject to Use meaningful variable names: for example x4,4,4 for the number of vertices of type (4, 4, 4) and c4 for the number of 4-cycles.
    (d) [5 marks] The optimal solution for the integer programming problem from (c) has n=56, all vertices of type (4,7,7), 14 4-cycles and 16 7-cycles. Why is this not realizable, and what constraint should be added to the integer programming problem to avoid this type of solution?
    (e) [10 marks] With the new constraint, the solution is n=32, with 8 ( 4, 4, 7) vertices, 24 ( 4, 7, 7) vertices, 10 4-cycles and 8 7-cycles. Draw a picture of a 32-vertex PCC graph realizing this solution as follows. Start in the middle with 4-cycle that is surrounded by four 7-cycles. Draw an embedding that has a 4-fold rotational symmetry about this inner 4-cycle.
  3. Here is one solution for the carbon-nitrogen problem. 
      0:   8   9  10
  1:   8  11  12
  2:   9  13  14
  3:  10  15  16
  4:  11  16  17
  5:  12  19  13
  6:  14  18  15
  7:  17  18  19
  8:   0  11   1
  9:   0   2  10
 10:   0   9   3
 11:   1   8   4
 12:   1   5  13
 13:   2  12   5
 14:   2  18   6
 15:   3   6  16
 16:   3  15   4
 17:   4   7  19
 18:   6  14   7
 19:   5  17   7

    (a) [5 marks] Draw a picture of the planar embedding represented by this rotation system placing vertex 2 in the middle of the picture. Drawing the picture like this will help you to see the symmetries. Make sure you draw it to show the rotational symmetry about vertex 2.
    (b) [5 marks] As per the PCC-graph problem, let the type of a vertex v of degree 3 be a triple (f1, f2, f3) where f1, f2 and f3 are the sizes of the 3 faces that v is in listed in sorted order. What types of vertices does this graph have and how many vertices of each type?
    (c) [5 marks] Compute the curvatures of each type of vertex in this graph. Is this graph a PCC graph? Why or why not?
    (d) [5 marks] Note that for any automorphism of the graph, vertices of a certain type can only be mapped to vertices of the same type. Use this information and your picture to determine the order of the automorphism group of this graph. Tell me what the symmetries look like by describing some operations that generate the group.
  4. (a) [5 marks] Two vertices u and v are in the same orbit with respect to the automorphism group if there is some automorphism that maps u to v. What are the orbits for the graph from the previous question? Hint: the graph has 3 orbits.
    (b) [5 marks] This permutation is an automorphism of the graph:
    (0 1 5 7 6 3)(2 4)(8 12 19 18 15 10)(9 11 13 17 14 16)
    Draw the non-uniform voltage graph that corresponds to this permutation. Label vertices
    (0 1 5 7 6 3) as a0, a1, a2, a3, a4, and a5,
    (2 4) as b0 and b1,
    (8 12 19 18 15 10) as c0, c1, c2, c3, c4, and c5, and
    (9 11 13 17 14 16) as d0, d1, d2, d3, d4, and d5.
    Use labels a, b, c, d on the corresponding nodes in the voltage graph.
  5. (a) [5 marks] The rotation system was numbered so that the smaller numbered vertices correspond to the nitrogens (the dominating set), and the rest of the vertices correspond to carbons (the graph induced by these is a perfect matching). Redraw your picture and color the nitrogens red and the carbons blue. Or if you do not have color, use a circle with white inside for the nitrogens and black for the carbons.
    (b) [5 marks] In constructing these solutions, my program starts with a small 3-regular graph, subdivides the edges, then adds chords. What is the small 3-regular graph that corresponds to this solution?
    (c) [5 marks] How many symmetries of the big graph map the nitrogens to the nitrogens? Justify your answer by describing these.
    (d) [5 marks] Recall that the number of different labelled dominating sets we get when applying the automorphisms to a given one is the group order of the embedding (without the nitrogens marked) divided by the number of automorphisms that map the set to itself. List the different labelled solutions that correspond to the given dominating set.