Friday Sep 29

Last time we defined a graph to be "connected" if there were a series of edges connecting any two vertices. But the graph with just one vertex has no edges. Surely we'd like it to be connected, though.

Fix #1: ask instead for a series of vertices.
Fix #2: ask for a series of edges connecting any two different vertices.

Union of sets, intersection, subset.

Def. A decomposition of a graph.

We started proving
Thm. A graph is connected iff it has no nontrivial decompositions.
Proof. => Assume G is connected. If it has a nontrivial decomposition... well, no it doesn't.
Next time: we'll go the other direction, and discuss proofs by contradiction; sections 1.4-1.6 of [FP].

Wednesday Sep 27

Converse, inverse, contrapositive. CAPalert example: "If it's not suitable for children, it's not suitable for adults!"

Definition. The deletion of a vertex from a graph.
Definition. A graph is connected if...
Question. Say G is regular, and v in V_G. When is the deletion again regular?
Answer (we didn't prove yet): iff v is connected to all, or to no, other vertices.

Monday Sep 25

Reiteration: "A => B" meaning more in English (actual causation) than it does in mathematese.

First taste of sets: they are determined by their elements, with no concept of order or repetition. Just in or out.
So {3,7} = {7,3} or {3,7,3,3,7}, but not {7} or {3,{7}}.
Set-forming notation.
Definition. A graph G is a pair of sets V_G, E_G where each element of E_G is a pair of (two different) elements of V.
(Frequent construction: "Definition. An X (noun) is a Y that Z.")
Definition. The degree of a vertex... a couple of versions.
Definition. A graph is regular if all vertices have the same degree... also a couple of versions.
(Frequent construction: "Definition. An X is Y (adjective) if it does Z.")

HW #1 due Monday Oct 2

1. Consider the following propositions about a function f(x,y) of two real numbers:

P1. for all x and y, f(x,y)=0

P2. for all x, there exists a y such that f(x,y)=0

P3. for all y, there exists an x such that f(x,y)=0

P4. there exists an x such that for all y, f(x,y)=0

P5. there exists a y such that for all x, f(x,y)=0

P6. there exist x and y such that f(x,y)=0.

a. For the following functions f, which of P1-P6 are true?

i. f(x,y) = 0 everywhere. ANSWER: "P1,P2,P3,P4,P5,P6 are all true."
ii. f(x,y) = x+y.
iii. f(x,y) = x³-xy²
iv. f(x,y) = y-x².
v. f(x,y) = x+y².
vi. f(x,y) = x²+y²-1

b. How do things change in part (a) if we allow x,y to be complex numbers?

2. Consider the following propositions about a function f(x,y,z) of three real numbers:

P1. for all x, there exists a y such that for all z, f(x,y,z)=0

P2. there exists an x such that for all y, there exists a z such that f(x,y,z)=0

a. Write down a function f(x,y,z) that satisfies P1 but not P2. Explain how to find the y required in P1, and why the x in P2 doesn't exist.

b. Write down a function f(x,y,z) that satisfies P2 but not P1. Explain how to find the x and z required in P2, and in P1 give an x for which there is no good y.

Warning: the reason this question is hard is that it has a bajillion possible answers, all equally good. Answering this question is more art than science.

3. Definition. A graph G is vague-ular if for all {v,w} in E_G, degree(v) = degree(w).

a. Prove that if a graph G is regular, it is vague-ular.

b. Show that the converse, "if a graph G is vague-ular, it is regular" is not true.

(What does this mean, "show this implication is not true"? It means give an explicit example of a graph that is vague-ular but not regular.)

The rest are from [FP], meaning, Fletcher and Patty. They're not as hard -- more just to help you check that you know what's going on.

1.1 #2, 3, 4, 8, 11
1.2 #21 (true, false, sometimes), 27
1.3 #52 (write these out with quantifiers)

Friday Sep 22

First class, partly about logistics, and the main goals.

And, or, implies (chapter 1.1, 1.2). The main thing to know about how mathematicians use the phrase "X implies Y" is that they don't really care about causality -- just that whenever X is true, Y will definitely also be true.

Quantifiers (chapter 1.3). The perils of reordering them, and how they interact with "not".

Fall 2006: Math 109, Mathematical Reasoning

Here's the web page for Math 109, where one finds the slower-changing facts about it. On this blog I'll keep a description of day to day occurrences, including homework assignments.

While I may enable commenting on some of these posts, it's not the surest way to get a rapid response from me -- much better to email me, "allenk", at the ucsd address. (Parse that, spambots!)