Last updated on

Quick link to assignments

*Course #: 11289**Class meets:*MWF 2:00-2:50PM in Yost 101

The meeting time may be modified if there is a need and all registered students agree.*Instructor:*Stanislaw J. Szarek (pronounced 'Shareck', more or less)*Office:*Yost 332*Office hours:*Currently M 1-2, W 10:30-11:20, or by appointment, or just drop by*Phone:*368-2913*E-mail:*szarek at cwru.edu (the preferred mode of communication)*WWW Home Page:*http://www.cwru.edu/artsci/math/szarek/*Class WWW Page (this page):*http://www.cwru.edu/artsci/math/szarek/MATH413/*Text:*: "Graph Theory" by J. Adrian Bondy and U.S.R. Murty; Graduate Texts in Mathematics 244, Springer 2008. ISBN 978-1-84628-969-9, 978-1-84628-970-5.

Notes will be supplied for additional topics as needed.*Note:*A "soft copy" of the book is available at no cost through CWRU Libraries. However, the hard copy is not excessively expensive ($69.95 directly from Springer and under $50 from Amazon).*Prerequisite:*MATH 201 or MATH 307

**Catalog Description:**
Building blocks of a graph, trees, connectivity, matchings, coverings,
planarity, NP-complete problems, random graphs, and expander graphs;
various applications and algorithms.

**The audience:** The course is primarily directed towards
advanced undergraduate or graduate
students in mathematics, computer science or operation research,
but it can also be a fun class for any student generally interested in mathematics
and familiar with basics of linear algebra.

**The subject:** Many real-world situations are conveniently
described by diagrams consisting of a collection of points (nodes) together
with lines or arrows connecting certain pairs of those points (edges).
Obvious examples
include transport or communication networks, but there are many more.
A mathematical abstraction of this type of situation is called a * graph.*
Graph Theory, besides being an important branch of Mathematics on its own right,
is of paramount importance in areas such as Computer Science or Operations Research,
particularly in the context of the so-called * Combinatorial Optimization.*

**The topics:** We will cover most of the first four chapters
from the textbook and a selection of topics from the remaining chapters.
Additional topics may include *graph Laplacians* and *expander graphs.*

**Computing:** Even though the topic of the course is closely related
to computing and algorithms, there will be no major computational component
in the coursework.
However, some topics/problems may be most easily approached/solved using software
packages such as *Mathematica* or *Matlab*, available through CWRUnet.

**Grades:** Your Final Grade in the course will be based on
Attendance/Homework/Class Participation (40%),
Midterm Exam (20%) and Final Exam (40%).

Students with special needs should contact
Educational Services for Students.

**Integrity:** It is OK (and indeed encouraged) to discuss homework assignments with fellow students. However, **any** submitted work must be your own.
Merely copying someone else's work is unethical,
a waste of time, and may be penalized.
(This includes copying solutions found on the internet.)
See
CWRU academic integrity policy.

Dr. Szarek's Home Page

Math/Stat Graduate Courses

Email webmaster -- Copyright 1993-2015 CWRU