Complexity and Networks

Uitgebreide vaknaam	Complexity and Networks
Leerdoelen	At the end of the course, the student is able to: 1. inspect whether a given graph is planar, Euler and unicursus; whether two given graphs are isomorphic; whether a given graph is bipartite; 2. construct a maximal matching for a given bipartite graph and on its basis, find a largest matching by applying Berge's magnifier; 3. find a maximal traffic flow in a transport network, not exceeding a given list of capacities; evaluate the transport capacity of a network cut, construct the increment graph and realise the Ford--Filkerson algorithm for finding a largest flow in a given network. Using the scheme for finding largest flows, find a least flow that exceeds the given loads; 4. bound controllable space by using graph partitions, verify whether a given set of nodes is a zero forcing set and apply the theory to specific classes of graphs in order to select leaders rendering the system controllable; 5. mathematically describe random graphs in terms of properties like connected components, average degree and diameter, is familiar with major examples like the Erdös-Renyi graph, the configuration model and the preferential attachment graph and is able to follow the proof of phase transition for connectivity in the Erdös-Renyi graph.
Omschrijving	This is an interdisciplinary course that presents different aspects of the theme Complexity and Networks from both the pure and applied mathematics points of view. The course consists of three parts. Part I of the course, by A.V.Kiselev, is Introduction to graphs and network flows. In three weeks, we study: * the notion of (un)directed graphs and graph isomorphisms, planar graphs (criterion), Euler and unicursus graphs (the Koenigsberg bridges problem); * bipartite graphs (Koenig's criterion), partitioning by using breadth first search, matchings (perfect, maximal, largest), the assignment problem (tourist guides and tourist groups) and Hall's theorem, Berge's magnifier theorem about finding a largest matching from a given maximal matching; * networks and network flows (maximal flow, largest flow, capacities and loads, least flow), the algorithm for finding a maximal flow; network cuts, the increment graph and the Ford--Fulkerson algorithm for finding a largest flow by using a given maximal flow. (The least flow problem is a bonus.) In the second part, by K. Camlibel, the notion of system controllability is discussed with emphasis on systems defined on graphs, diffusively coupled leader/follower systems, and concepts such as controllable space, leader selection, and targeted controllability. In the third part, by D. Valesin, the topic is the Erdös-Renyi random graph model; the main result that is stated and proved is the phase transition, with respect to the connectivity probability parameter, of the size of the largest connected component of this graph.
Uren per week
Onderwijsvorm	Hoorcollege (LC), Werkcollege (T)
Toetsvorm	Opdracht (AST) (The assessment consists of 3 homework assignments, one for each part of the course. The final grade is the average of the grades of the 3 homework grades, provided that all grades are above 4. If one of the homework grades is 4 or less then the final grade is the minimum of the homework grades.)
Vaksoort	master
Coördinator	prof. dr. D. Rodrigues Valesin
Docent(en)	prof. dr. M.K. Camlibel , A.V. Kiselev ,prof. dr. D. Rodrigues Valesin
Verplichte literatuur	Titel Auteur ISBN Prijs (suggestion, not mandatory) Graph theory with applications. 1976 J.A.Bondy and U.S.R.Murty (suggestion, not mandatory) Random graph dynamics. Vol. 200, no. 7. Cambridge: Cambridge university press, 2007. Durrett, Richard (suggestion, not mandatory) Synchronization in Complex Networks, Physics Reports, vol. 469, pp. 93-153, 2008. A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, C. Zhou, (suggestion, not mandatory) "Random graphs and complex networks." Available on http://www.win.tue.nl/rhofstad/NotesRGCN.pdf (2009). Van Der Hofstad, Remco (suggestion, not mandatory) Graph theory. 2008 J.A.Bondy and U.S.R.Murty 978-1-84628-969-9 (suggestion, not mandatory) Theory of graphs. 1962 Oystein Ore
Entreevoorwaarden	The course assumes prior knowledge in: - Real and complex analysis - Probability theory - Linear algebra (vector spaces, invariant subspaces, quotient spaces, eigenvalues, eigenvectors) - Fourier series - Dynamical systems (equilibria, linear stability) - Systems theory (state and controllability) - Programming skills
Opmerkingen	Literature: Part 1: References: - Introduction to Modern Dynamics: Chaos, Networks, Space and Time. D. D. Nolte, Oxford University Press, 2015. - Synchronization in Complex Networks. A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, C. Zhou, Physics Reports, vol. 469, pp. 93-153, 2008. Part 3: Main reference: - Van Der Hofstad, Remco. "Random graphs and complex networks." Available on http://www.win.tue.nl/rhofstad/NotesRGCN.pdf (2009). Additional reference: - Durrett, Richard. Random graph dynamics. Vol. 200, no. 7. Cambridge: Cambridge university press, 2007. Part 4: Reference: - Notes on Rigidity Theory, James Cruickshank This course was registered last year with course code WMMA16000
Opgenomen in	Opleiding Jaar Periode Type MSc Applied Mathematics: Computational Mathematics  ( MSc Applied Mathematics: Computational Mathematics ) - semester I a verplicht MSc Applied Mathematics: Systems and Control  (MSc Applied Mathematics: Systems and Control) - semester I a verplicht MSc Courses for Exchange Students: AI - Computing Science - Mathematics - semester I a MSc Mathematics and Physics (double degree)  (Mathematics and Complex Dynamical Systems (45 ects)) - semester I a verplicht MSc Mathematics: Mathematics and Complex Dynamical Systems - semester I a verplicht MSc Mathematics: Science, Business and Policy  (MSc Mathematics: Science, Business and Policy) - semester I a verplicht MSc Mathematics: Statistics and Big Data  (MSc Mathematics: Statistics and Big Data) - semester I a verplicht