Difference between revisions of "MAT4323"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
 
(7 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
''Contents''
 
''Contents''
−
(1) Basic counting principles: Permutations, combinations, binomial coefficients, arrangements with repetitions, and the Inclusion-Exclusion principle.
+
 
−
(2) Graph models: Isomorphisms, edge counting
+
Graph models (Isomorphisms, edge counting, planar graphs),
−
(3) Planar graphs.
+
Covering circuits and graph colorings (Euler circuits, Hamilton circuits, graph colorings),
−
(4) Covering circuits and graph colorings: Euler circuits, Hamilton circuits, graph colorings, Ramsey's theorem
+
Network algorithms (Shortest path, minimum spanning trees, matching algorithms, transportation problems),
−
(5) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems.
+
Ramsey's Theorem and Ramsey numbers.
−
(6) Order relations: Partially ordered sets, totally ordered sets, extreme elements (maximum, minimum, maximal and minimal elements), well-ordered sets, maximality principles.
 
  
 
== Sample textbooks ==  
 
== Sample textbooks ==  
Line 16: Line 15:
  
 
[2] Alan Tucker, ''Applied Combinatorics'', Freely available online [https://www.isinj.com/mt-usamo/Applied%20Combinatorics%20(6th%20Edition)%20by%20Alan%20Tucker%20Wiley%20(2012).pdf here]
 
[2] Alan Tucker, ''Applied Combinatorics'', Freely available online [https://www.isinj.com/mt-usamo/Applied%20Combinatorics%20(6th%20Edition)%20by%20Alan%20Tucker%20Wiley%20(2012).pdf here]
 +
 +
[3] Gary Chartrand and Ping Zhang, ''A First Course in Graph Theory'', Dover Books on Mathematics, 2012.
  
  
Line 31: Line 32:
 
! Week !! Topic !! Sections from Tucker's book !! Subtopics !! Prerequisite
 
! Week !! Topic !! Sections from Tucker's book !! Subtopics !! Prerequisite
 
|-
 
|-
−
|  1-2 
+
|  1-3   
−
|| [[Basic counting principles]]
 
−
|| 5.1-5.5
 
−
|| Permutations, combinations, binomial coefficients, arrangements with repetitions
 
−
|| MAT1313, CS2233/2231, or instructor consent.
 
−
|-
 
−
|  3  
 
−
|| [[Inclusion-Exclusion Principle]]
 
−
|| 8.1-8.2
 
−
|| Counting with Venn diagrams.
 
−
|-
 
−
|  4-6    
 
 
|| [[Graph models]]
 
|| [[Graph models]]
 
|| 12.1-12.3
 
|| 12.1-12.3
 
|| Isomorphism, edge counting, planar graphs.
 
|| Isomorphism, edge counting, planar graphs.
 
|-
 
|-
−
|  7-8    
+
|  4-6    
 
|| [[Covering circuits]]
 
|| [[Covering circuits]]
 
|| 2.1-2.4
 
|| 2.1-2.4
 
|| Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
 
|| Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
 
|-
 
|-
−
|  9-10    
+
|  8-9   
 
|| [[Trees]]  
 
|| [[Trees]]  
 
|| 3.1-3.4
 
|| 3.1-3.4
 
|| Search trees, spanning trees, the Traveling Salesman Problem
 
|| Search trees, spanning trees, the Traveling Salesman Problem
 
|-
 
|-
−
|  11-13    
+
|  10-12    
 
|| [[Network algorithms]]  
 
|| [[Network algorithms]]  
 
|| 4.1-4.5
 
|| 4.1-4.5
 
|| Shortest path , minimum spanning trees, matching algorithms, transportation problems.
 
|| Shortest path , minimum spanning trees, matching algorithms, transportation problems.
 +
|-
 +
| 13-14
 +
|| [[Finding order within chaos]]
 +
||
 +
|| Ramsey's Theorem and Ramsey numbers
 
|}
 
|}

Latest revision as of 09:49, 21 April 2023

Catalog entry

Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.

Contents

Graph models (Isomorphisms, edge counting, planar graphs), Covering circuits and graph colorings (Euler circuits, Hamilton circuits, graph colorings), Network algorithms (Shortest path, minimum spanning trees, matching algorithms, transportation problems), Ramsey's Theorem and Ramsey numbers.

Sample textbooks

[1] Vladlen Koltun, Discrete Structures, Lecture Notes, Stanford University, 2008. Freely available online here

[2] Alan Tucker, Applied Combinatorics, Freely available online here

[3] Gary Chartrand and Ping Zhang, A First Course in Graph Theory, Dover Books on Mathematics, 2012.






Topics List

Week Topic Sections from Tucker's book Subtopics Prerequisite
1-3 Graph models 12.1-12.3 Isomorphism, edge counting, planar graphs.
4-6 Covering circuits 2.1-2.4 Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
8-9 Trees 3.1-3.4 Search trees, spanning trees, the Traveling Salesman Problem
10-12 Network algorithms 4.1-4.5 Shortest path , minimum spanning trees, matching algorithms, transportation problems.
13-14 Finding order within chaos Ramsey's Theorem and Ramsey numbers
Retrieved from "https://mathresearch.utsa.edu/wiki/index.php?title=MAT4323&oldid=5206"