Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MAT 344

2022 S

Problem Set 3

Graphs and Posets

Learning Objectives

These problems relate to the course learning outcomes:

● Select and justify appropriate tools to analyze a counting problem,

● Analyze a counting problem by proving an exact or approximate enumeration, or a method to compute one efficiently; and

●  Construct counting problems which show the usefulness or limitations of combinato- rial tools.

1. Let P be a poset on n points with height h = n - 3, width w = 3, and the fewest possible number of relations.  Specifically, P has x1  with only the reflexive relation, x2  5 x3  with no other (non-reflexive) relations, and a chain of length n - 3.  Give a combinatorial proof to show that the number of linear extensions of P is both

│ 、│、= 、+ h + 1、 │h1(+) 3、.

2. For positive integers n and m, give a formula and a justification for:

(a) The number of subgraphs Cm  in a labelled K。.  To help check, K5  contains 20

copies of C3 , and 30 copies of C4 .

(b) The number of subgraphs Pm in a labelled K。﹐。. The bipartite graph K3 ﹐ 3  contains

72 copies of P5 ; 72 of P6 ; and 0 of P7 .

3. An electrical network contains many components connected by wires.  When it is working correctly, current moves between components along the wires. For example, from component A to B along w1  then from B to C along w2 . Sometimes it does not work correctly and the current “arcs”: it jumps from w1 to w2 without reaching B. This can happen even if A and C are directly connected by another wire. Recently, an arc in the hydro vault of Myhal caused a power disruption in the building for a week. Show that if the network has n components, {C1 , . . . , C。}, and if the number of connections at Ci  is di , then the number of possible arc locations is ╱2(dA)←+╱2(de)←+ . . . +╱← . Note that the values of di  may be different.

4. Let a, b be positive integers, and set n = 2α 3b .  Define a poset P whose points are positive divisors of n (including 1 and n), with the relation x 5 y if and only if x divides

y. Find, with justification, the height and width of this poset. For example, if a = 2 and b = 3, then 1 5 2 5 6 5 18 5 36 5 108 is a maximal chain, so the height is 6, and {4, 6, 9} is a maximal anti-chain, so the width is 3.

5. A graph is called d-regular if every vertex has the same degree, d. Show that the edges of a 4-regular graph can be labelled with -1 or 1 so that the sum of the labels at each vertex is 0. Give an example of a 6-regular graph where this is impossible, and explain why it cannot be done.

Let denote the number of proper colourings of (the cyclic graph with vertices) using

at most 3 colours. Find a recurrence for , and use it to determine 9. We have 3=6 and

12=4098 to check your recurrence. You can use any results from tutorials.