Phd program
More detailed display of contents (week-by-week)
Yüklə 233,54 Kb.
|
- Bu səhifədəki naviqasiya:
- Course Level
- More detailed display of contents (week-by-week)
- The learning outcomes of the course
- No. of Credits
- The goals of the course
- 18) LARGE SPARSE GRAPHS, GRAPH CONVERGENCE AND GROUPS Course coordinator
- More detailed display of contents
- Reference
More detailed display of contents (week-by-week): Week 1: Historical introduction to the formalism of canonical commutation relation(contribution of Heisenberg, Schrödinger and von Neuman in 1920's) Week 2: A short introduction to C*-algebras, their states and representations (Gelfand-Naimark theorems, GNS-construction, tensor product structure) Week 3: The C*-algebra of the canonical commutation relation, CCR (existence and uniquenes) Week 4-5: The concept of symmetric Fock space (definition, second quantization, important examples of unbounded operators, exponential vectors) Week 6: The Fock representation of the CCR (detailed study of the one-dimensional case, tensor product) Week 7-9: States on CCR (Gaussian states 2-point function. relation to classical probability) Week 10-11: Central limit theorem (statement and proof, maximization of entropy when 2-point function is fixed, an introduction to some unsolved problems) Week 12: Schrödinger representation (introduction to Hermite polinomials, the P and Q operators, their complementary relation) Reference: D. Petz:The algebra of the canonical commutation relation, Leuven University Press, 1990. 11)ENUMERATION Course Coordinator: Ervin Gyori No. of Credits: 3, and no. of ECTS credits: 6. Prerequisites:Topics in Combinatorics Course Level: advanced PhD Brief introduction to the course: The main theorems of Enumeration are presented, and their connections to number theory. The goals of the course: The main goal of the course is to introduce students to the main topics and methods of Enumeration The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. More detailed display of contents (week-by-week):
References: 1. D.E. Knuth, The Art of Computer programming, Third Edition (Reading, Massachusetts: Addison-Wesley, 1997. 2. R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics: a Foundation for Computer Science, Addison-Wesley, Reading, U.S.A., 1989. 3. H.S. Wilf: Generatingfunctionology, Academic Press, 1990. 4. G.E. Andrews, The theory of partitions, Addison-Wesley, 1976. 12) EXTREMAL COMBINATORICS Course Coordinator: Ervin Gyori No. of Credits: 3, and no. of ECTS credits: 6. Prerequisites:Topics in Combinatorics
The main theorems of Extremal Combinatorics are presented, like Ramsey theory, or Szemeredi’s theorem. The goals of the course: The main goal of the course is to introduce students to the main topics and methods of Extremal Combinatorics. The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. More detailed display of contents (week-by-week):
References: 1. B. Bollobás: Extremal Graph Theory, Academic Press, London, 1978. 2. R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, Wiley, New York, 1980. 13)RANDOM METHODS IN COMBINATORICS Course coordinator: Gyula Katona No. of Credits: 3, and no. of ECTS credits: 6. Prerequisites: - Course Level: advanced PhD Brief introduction to the course: Introducing the random method in combinatorics. Proving the existence of certain combinatorial structures, or proving lower estimates on the number of such structures. Enumeration method, expectation method. Second momentum method, Lovász Local Lemma. Random and pseudorandom structures. The course is suggested to students oriented in combinatorics and computer science. The goals of the course: To show the main results and methods of the theory. The learning outcomes of the course: The students will know the most important results of the theory, they will be able follow the literature, apply these results in practical cases and create new results of similar nature. More detailed display of contents: Week 1: The basic method, applications in graph theory and combinatorics. Week 2: Applications in combinatorial number theory. Week 3: Probabilistic proof of the Erdős-Ko-Rado theorem and the Bollobás theorem. Week 4: Application in Ramsey theory. Week 5: The second moment method. The Rödl Nibble. Week 6: The Lovász Local Lemma. Week 7: Applications of LLL in Porperty B, Ramsey theory and geometry. Week 8: Correlation inequalities: Ahlswede-Daykin and FKG inequalities. Week 9: Martingales and tight concentration. Week 10: Talagrand’s inequality and Kim-Vu’s polynomial concentration. Week 11: Random graphs. Week 12: Pseudorandom graphs. References: 1. N. Alon, J.H. Sepncer: The Probabilitstic Method, John Wiley & Sons, 1992. 2. B. Bollobás: Random Graphs, Academic Press, 1985. 3. P. Erdős: The Art of Counting, Cambridge, MIT Press, 1973. 4. P. Erdős: Joel Spencer: Probabilitstic Methods in Combinatorics, Academic Press, 1974. 14) INTRODUCTION TO THE THEORY OF COMPUTING Course Coordinator: Gyula Katona No. of Credits: 3, and no. of ECTS credits: 6 Prerequisites: - Course Level: introductory PhD Brief introduction to the course: The main ideas of the Theory of Algorithms are presented among others about NP completeness in general/ The goals of the course: The main goal of the course is to have a basic understanding of the Theory of Algorithms The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. More detailed display of contents (week-by-week):
Reference: T. H. Cormen, C. L. Leiserson and R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990. 15) COMPLEXITY THEORY
Course Coordinator: Miklos Simonovits Prerequisite: Theory of Computing
The main theorems of Complexity Theory are presented among others about the classes NP, P, NL, PSPACE, or randomization. The goals of the course: The main goal of the course is to introduce students to the main topics and methods of Complexity Theory. The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. More detailed display of contents (week-by-week): Week 1-2 Formal models of computation: Turing machines, RAM machines. Week 3-4 Reduction, complete languages for NP, P, NL, PSPACE. Savitch’s theorem. Week 5-6 Diagonal method: time- and space hierarchy. Week 7-8 Randomization, randomized complexity classes, their relation to deterministic/non-deterministic classes, examples. Week 9-10 Communication complexity, deterministic, non-deterministic, relation to each other and to matrix rank. Week 11-12 Decision trees: deterministic, non-deterministic, randomized, sensitivity of Boolean functions. Reference: M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company Boston, 1997. 16) BLOCK DESIGNS Course coordinator: Tamas Szonyi No. of Credits: 3, and no. of ECTS credits: 6 Prerequisites:Topics in combinatorics, Topics in algebra Course Level: intermediate PhD Brief introduction to the course: After a quick introduction to the theory of block designs and strongly regular graphs, the main emphasis will be on the interplay between these two, and applications to other areas of mathematics like coding theory, group theory or extremal graph theory. Several techniques will be presented varying from combinatorial and geometrical methods to algebraic ones, like eigenvalues, polynomials, linear algebra and characters. Because of the quick introduction at the beginning, the lectures should be useful for both those not familiar with the subject and those who have already attended an introductory course on symmetric combinatorial structures. The goals of the course: Besides introducing the audience to areas with nice open problems, the main goal is to show different proof techniques in combinatorics. The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. More detailed display of contents (week-by-week): 1. Designs: basic definitions, existence, examples, square designs, extendability, Hadamard matrices and designs, projective planes, Latin squares, sharply two-transitive permutation sets. 2. Strongly regular graphs: definitions, examples, integrality conditions, necessary conditions for the existence. 3. The existence of non-trivial t-designs with t>5. Teirlinck’s theorem 4. Witt designs and Mathieu groups. 5. Quasi-residual designs. The Hall-Connor theorem. 6. Designs and projective geometries. 7. Difference sets. Multiplier theorems. 8. Basics of coding theory. 9. Codes and designs. 10. 1-factorizations of complete graphs and designs, Baranyai’s theorem. 11. Moore graphs. Generalized polygons, the Feit-Higman theorem. 12. Moore graphs and (k,g)-graphs. Constructions and bounds. References: 1. J. H. Van Lint, R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001. 2. P. J. Cameron, J. H. van Lint, Designs, Graphs, Codes and their Links, Cambridge University Press, 1991. 17) HYPERGRAPHS, SET SYSTEMS, INTERSECTION THEOREMS Course coordinator: Gyula Katona No. of Credits: 3, and no. of ECTS credits: 6 Prerequisites:- Course Level: advanced PhD Brief introduction to the course: It gives the most important results and methods in extremal set theory. Largest inclusion-free and intersecting families, their combinations. Minimum size of the shadow. Methods: shifting, transformation, permutation, cycle, algebraic. The course is suggested to students oriented to combinatorics and computer science. The goals of the course: To show the main results and methods of the theory. The learning outcomes of the course: The students will know the most important results of the theory, they will be able follow the literature, apply these results in practical cases and create new results of similar nature. More detailed display of contents: Week 1: Inclusion-free families, antichains, 3 proofs of the Sperner theorem Week 2: LYM (YBLM)-inequality, case of equality. Week 3: Maximum size of the intersecting families. Week 4: Erdős-Ko-Rado theorem for the uniform intersecting families. Cycle method. Week 5: Shifting method, properties preserved by shifting. Left shifted families. Week 5: Shifting method for the Erdős-Ko-Rado theorem. Week 6: Minimum of the size of the shadow relative to an l-intersecting family. Week 7: Maximum size of an l-intersecting family. Week 8: Minimum size of the shadow. Week 9: Discrete isoperimetric theorem. Week 10: The algebraic method. “Even city”. Week 11: Families with intersections of one fixed size. Erdős-DeBruijn theorem. Week 12: Largest families with intersection of sizes in a given subset of integers. Ray-Chaudhury-Wilson theorem. Reference: Konrad Engel: Sperner Theory, 18) LARGE SPARSE GRAPHS, GRAPH CONVERGENCE AND GROUPS Course coordinator: Miklós Abért No. of Credits: 3 and no. of ECTS credits: 6 Prerequisites: Course Level: intermediate PhD Brief introduction to the course: A family of finite graphs is sparse, if the number of edges of a graph in the family is proportional to the number of its vertices. Such families of graphs come up frequently in graph theory, probability theory, group theory, topology and real life applications as well. The emerging theory of graph convergence, that is under very active research in Hungary, handles large sparse graphs through their limit objects (examples are unimodular random graphs and graphings). The topic is related to group theory, more precisely, the theory of residually finite and amenable groups and their actions in various ways. A general tool used throughout the course is spectral theory of graphs and groups. The goals of the course: The course gives an introduction to the emerging theory of graph convergence, together with its connections to group theory and ergodic theory. The course also serves as a theoretical background for network science. The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. More detailed display of contents: Week 1. Space of rooted graphs, neighborhood sampling, invariant processes on vertex transitive graphs Week 3. Basic spectral theory of graphs, expander graphs and random walks Week 4. Spectral measure and the eigenvalue distribution Week 5. Random rooted graphs, Benjamini-Schramm convergence, property testing Week 6. The tree entropy is testable Week 7. Residually finite, amenable and sofic groups Week 8. Kesten’s theorem Week 9. Ergodic theory of group actions and graphings Week 10. Hyperfiniteness Week 11. Coloring entropy, root measures and the matching ratio Week 12. Invariant random subgroups Reference: L. Lovasz: Large networks and graph limits, AMS, 2012. 19) SELECTED TOPICS IN GRAPH THEORY Course Coordinator: Ervin Gyori No. of Credits: 3, and no. of ECTS credits: 6 Prerequisites: - Course Level: advanced PhD Brief introduction to the course: An advances course on Graph Theory is presented. The goals of the course: The main goal of the course is to enable the students to become experts on current topics in Graph Theory. The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. Contents: The subject of this course changes from time to time depending on the fields of interest of students. 20) COMPUTATIONAL GEOMETRY Course Coordinator: Gabor Tardos No. of Credits: 3, and no. of ECTS credits: 6 Prerequisites:- Course Level: introductory PhD Brief introduction to the course: The main notions and theorems of Combinatorial Geometry are presented, like Voronoi diagram, Delaunay triangulations, and Applications in Computer Science, Robotics, Computer graphics. The goals of the course: The main goal of the course is to introduce students to the main topics and methods of Computational Geometry. The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. More detailed display of contents (week-by-week):
Reference: M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf: Computational Geometry - Algorithms and Applications, Springer, Berlin, 1997. 21) COMBINATORIAL OPTIMIZATION Course coordinator: Ervin Győri No. of Credits: 3and no. of ECTS credits: 6 Prerequisites:- Course Level: introductory PhD Brief introduction to the course: Basic concepts and theorems are presented. Some significant applications are analyzed to illustrate the power and the use of combinatorial optimization. Special attention is paid to algorithmic questions. The goals of the course: One of the main goals of the course is to introduce students to the most important results of combinatorial optimization. A further goal is to discuss the applications of these results to particular problems, including problems involving applications in other areas of mathematics and practice. Finally, computer science related problems are to be considered too. The learning outcomes of the course: By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general. They will learn how to use these tools in solving everyday life problems as well as in software developing. More detailed display of contents: Week 1: Typical optimization problems, complexity of problems, graphs and digraphs Week 2: Connectivity in graphs and digraphs, spanning trees, cycles and cuts, Eulerian and Hamiltonian graphs Week 3: Planarity and duality, linear programming, simplex method and new methods Week 4: Shortest paths, Dijkstra method, negative cycles Week 5: Flows in networks Week 6: Matchings in bipartite graphs, matching algorithms Week 7: Matchings in general graphs, Edmonds’ algorithm Week 8: Matroids, basic notions, system of axioms, special matroids Week 9: Greedy algorithm, applications, matroid duality, versions of greedy algorithm Week 10: Rank function, union of matroids, duality of matroids Week 11: Intersection of matroids, algorithmic questions Week 12: Graph theoretical applications: edgedisjoint and covering spanning trees, directed cuts Reference: E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Courier Dover Publications, 2001 or earlier edition: Rinehart and Winston, 1976 22) THEORY OF ALGORITHMS Course Coordinator: Miklos Simonovits Yüklə 233,54 Kb. Dostları ilə paylaş:
|