The CIMPAIndonesia School on Extrema Problems and Hamwill contain six minicourses: 1. BASIC NOTIONS ON GRAPHS by Joe Ryan
This lecture gives the fundamental elements and concepts of graph theory. The School assumes no prior knowledge of Graph Theory. The topics that are covered by this lecture include: a) Introduction to the Theory of Graphs. History and Overview, Elements of Graphs and Digraphs, Applications of Graphs and Digraphs. b) Walks, Paths and Cycles. Euler Trails, Walks and Paths, Complete Graphs and Complete Bipartite Graphs, Hamiltonian Paths and Cycles, Weighted Graphs and Shortest Paths. c) Trees. Properties of Trees, Spanning Trees, Applications of Trees. d) Distance Properties of Graphs. Centre and Periphery, Eccentricity, Applications in Communication Networks, Small World Networks. e) Connectivity. Cuts, Edge Connectivity, kconnectivity, Connectivity in Digraphs. f) Graph Coloring and Labeling. Edge Colouring, Tournaments, Vertex Colouring, Scheduling, Irregular labeling, Sum labeling. g) Planarity. Plane and Planar Graphs, Euler’s Theorem, Maps and Planarity. h) Matrices. Adjacency Matrices, Eigenvalues in Graphs, Spectral Analysis
2. EXTREMAL PROBLEMS IN MOORE (DI)GRAPHS by Mirka Miller
The principal objective of this, the second of five minicourses, is to introduce all participants to one of the important unsolved problems in Graph Theory, the degree/diameter problem, also referred to as the N(d,k) problem, or the (d,k) problem. Building on the fundamental elements and concepts presented in the first minicourse, we expect to cover this problem area in a reasonable depth and to give the students an uptodate knowledge, as well as to introduce them to the intricacies present in this research area.
The list of topics presented below is an approximate plan for the minicourse.
a) Introduction to the Degree/Diameter Problem. History and overview, Basic terminology, Examples of extremal graphs and digraphs. b) Undirected Moore graphs. Characterization of Moore Graphs, Proof of the Nonexistence of Moore Graphs for Most Values of the Parameters, Open Problems c) Undirected Graphs Close to Moore Bound. Regularity of Undirected Graphs Close to Moore Bound, Graphs with Defect 1, Graphs with Defect 2 and More, Open Problems d) Large Undirected Graphs. Construction Methods, Table of Largest Known Graphs, Open Problems e) Directed Moore Graphs. Complete Characterisation of Moore Digraphs, Proof of the Nonexistence of Moore Digraphs for Maximum Outdegree and Diameter Greater than 1, Open Problems. f) Directed Graphs Close to Moore Bound. Digraphs with Defect 1, Diregularity of Almost Moore Digraphs, Digraphs with Defect 2 and More, Open Problems. g) Large Directed Graphs. Construction Methods, Upper and Lower Bounds, Graphs and Digraphs with Relaxed Parameters, Open Problems.
3. GRAPHS LABELINGS by Anna Llado
The area of graph labeling is an active area of research in graph theory with hundreds of references in the literature. The main problem is to assign a set of integers or the elements of a group to elements of the graph (vertices, edges or both) such that some arithmetic properties hold. One of the motivations is to address long—standing conjectures on decompositions of graphs, like the celebrated Ringel conjecture on the decomposition of the complete graph by isomorphic copies of a given tree. However the area of graph labelings has many applications both within mathematics and to several areas of computer science and communication networks. The course plans to cover the main results in the area and discuss several of its applications.
a. Decomposition of complete graphs. The RingelKotzig conjecture and graceful labelings. Rosa's four classes of labelings. Basic results on graceful labelings.
b. Decomposition of complete bipartite graphs. The Haggkvist conjecture. Bigraceful labelings. Classes of bigraceful trees.
c. General and approximated results on graceful and bigraceful labelings. Every tree is a large subtree of a bigraceful tree. Every tree is homomorphic to a graceful tree. Trees with even degrees. Trees with large growth.
d. The polynomial method. Trees with large growth. Results on the number of (bi)graceful labelings. Decomposing the complete bipartite graph minus a matching.
e. Magic graphs. Basic definitions and results. Sidon sets and weak Sidon sets. Largest cliques in magic graphs. Labelings with pairwise distinct edgevalues.
f. Hmagic graphs. Basic definitions and results. Covering by paths, cycles and stars. Equipartitions of integer intervals. Face magic graphs. Relation with other decomposition problems.
g. Related labeling problems and their connections. Applications to communication networks and to computer science.
4. HAMILTONIAN GRAPH THEORY by Evelyne Flandrin
This course will cover the main results in the area and discuss several of its open problems:
a. Basic concepts. Cycles and paths in graphs, Hamiltonian graphs, NPcompleteness of the Hamiltonian problem. b. Basic techniques. Degree conditions and longest cycle techniques, Toughness and the Chvátal’s conjecture, Closure techniques (based on vertex degrees (BondyChvátal’s closure and kstability, stronger closures, based on structural conditions). c. Strong Hamiltonian properties. Pancyclicity, Hamilton connectedness, cycle extendability. d. Relaxations of hamiltonicity. Traceability, prismhamiltonicity, 2factor with limited number of components, spanning kwalk, ktrestle. e. Hamiltonicity in special classes of graphs. Squares, classes of graphs defined in terms of pairs of forbidden subgraphs, line graphs and clawfree graphs, closure and contraction techniques for clawfree graphs and line graphs. f. Some open problems and conjectures.
5. EXTREMAL GRAPH THEORY by Oriol Serra
The general problem of classical extremal graph theory asks for the maximum number of edges a graph can have if it does not contain a given graph as a subgraph. The first result in the area is the Theorem of Turán which address the problem for graphs not containing a complete graph of a given order. One of the major results are the ErdösSimonovits and the ErdösStone theorems which relates extremal problems for a familiy of avoided graphs to their chromatic number.
The course contains also applications of extremal problems to the theory and algorithms of combinatorial group testing. Group testing arises in largescale blood testing for viruses such as HIV, in connection with mapping of genomes or the identification of defective products. Some of these applications will be discussed in the course.
a) The Turán theorem and the Turán graphs. b) Extremal problems for cycles, paths and trees. c) Extremal roblems for multipartite complete graphs: the ErdösStone theorem. d) Chromatic partitions and closeness to the Turán graph. The ErdösSimonovits theorem. e) The Removal Lemma. The Szemerédi Regularity Lemma. f) Removal Lemma and group testing: applications to experimental designs and to coding theory.
6. RAMSEY NUMBERS by Edy Tri Baskoro Ramsey theory was introduced in the context of the problem of finding a regular procedure to determine the consistency of any given logical formula (1928). The aim of the study was to give a decision procedure for the sentences of propositional logic. The Ramsey theory became famous after Paul Erdos and George Szekeres (1935) applied it in graph theory. In graph theory, the 'classical' Ramsey number is defined basically the following. For any positive integers m and n, the classical Ramsey number is defined as the smallest integer R = R(m, n) such that every graph F on R vertices will satisfy the following condition: either F contains a complete graph K_{m} on m vertices as a subgraph or the complement of F has a complete graph K_{n} on n vertices as a subgraph.
The research on finding the exact values of classical Ramsey numbers R(m,n) has received a lot of attention. However, the results are still far from satisfactory. Since firstly introduced, there are only nine exact Ramsey numbers known so far. In general, determining the exact values of Ramsey numbers is a difficult problem. However, some 'nontrivial' lower and upper bounds for these numbers have been obtained.
Classical Ramsey number has been generalized in various ways, for instance graph Ramsey numbers by releasing the completeness in the prescribed conditions, size Ramsey numbers by considering the minimal size of the graph rather than the order, and in some other types of generalizations.
This course will cover the main results and open problems in these various types of Ramsey numbers and Ramseyminimal graphs. The list of topics is as follows:
a. Classical Ramsey numbers. Known results on classical Ramsey numbers. Schur number, Van der Waerden number, and its relations to Ramsey numbers. b. Graph Ramsey numbers. ChvatalHarary bound, Recent developments on graph Ramsey numbers for various combination of graphs. c. Size Ramsey numbers. Known results and open problems on size ramsey numbers. d. Ramseyminimal graphs. Known results and open peblems on (G,H)Ramsey minimal graph for various combinations of G and H.
