International Francqui chair Brendan McKay
From early June 2019 till early September 2019, prof. Brendan McKay (Australian National University) will be in Belgium as an International Francqui Professor. This chair is generously funded by the Belgian Francqui-Foundation. The host of Brendan McKay's stay in Belgium is the Department of Applied Mathematics, Computer Science and Statistics at Ghent University, in collaboration with the Computer Science Department at the University of Mons and the Department of Computer Science at the Université Libre de Bruxelles.
Brendan McKay
Prof. Brendan McKay obtained his PhD in 1980 at the University of Melbourne. Then he became Assistant Professor at Vanderbilt University until he obtained a faculty position at the Australian National University in 1983. The core topic of Brendan McKay's research is "computational graph theory" and he is the world leader in this field of research. His program “nauty” is part of practically every software system dealing with isomorphisms of graphs, his graph generators are used for research in mathematics, physics and chemistry and his mathematical results - often obtained with the help of computational methods - were published in practically all top journals in combinatorics.
He gave more than 60 invited talks, amongst them such prestigious talks as at the "International Congress of Mathematicians 2010". Furthermore, his articles (in total more than 200) have been cited more than 9000 times - which is quite unusual for mathematics - and he is editor and on the editorial board of several influential mathematical journals.
Though one may call "computational graph theory" the core topic of his research, he also obtained several important results in other fields of science and is famous even outside science for refuting the "bible code" claim. This research even resulted in several appearances in newspapers, on the radio and TV.
Inaugural lecture
A scientist's adventure in pseudoscience: the strange case of the Bible Codes
- Tuesday 4 June 2019, 16h00.
- Ghent University, Campus Sterre, Building S9, Auditorium A2.
Krijgslaan 281, 9000 Ghent.
Google maps - Download the invitation poster
- The lecture will be followed by a reception, please confirm your attendance by 28 May 2019.
A scientist's adventure in pseudoscience: the strange case of the Bible Codes
Over the centuries, many claims have been made of numerical patterns of miraculous nature hidden within the text of sacred writings, including the Jewish, Christian and Islamic scriptures. Usually the patterns involve counting of letters and words, or calculations involving numerical equivalents of the letters.
Until recently, all such claims were made by people with little mathematical understanding and were easily explained. This situation changed when a highly respected Israeli mathematician Eliyahu Rips and two others published a paper in the academic journal Statistical Science claiming to prove that information about medieval Jewish rabbis was encoded in the Hebrew text of the Book of Genesis. The journal reported that its reviewers were "baffled".
The paper in Statistical Science spawned a huge "Bible Codes" industry, complete with best selling books, TV documentaries, and even an adventure movie.
The talk will reveal the inside story of the Codes and the people behind them, from their inception through to their refutation.
This inaugural lecture is the first lecture in a series of lectures that Prof. McKay will be giving at various Belgian universities. The full programme of this lecture series can be consulted below.
Francqui lecture series by Brendan McKay
-
Graph generation without isomorphs
Date: Tuesday 11 June 2019, 14h00
Venue: Université catholique de Louvain
Location: Euler Building, room A.002, Avenue Georges Lemaître 4 - bte L4.05.01, 1348 Louvain-la-Neuve
Abstract
We consider the problem of exhaustively generating families of graphs in a way that avoids isomorphic graphs while at the same time requiring very little memory even for very large families. Such algorithms are important for listing chemical isomers and for many other applications. As an example we present several algorithms for generating fullerenes (the "buckyball" molecules made only of carbon atoms).
-
Practical graph isomorphism
Date: Tuesday 18 June 2019, 14h00
Venue: University of Mons
Location: Da Vinci building, Salle du Conseil, Avenue Maistriau 15, 7000 Mons
Abstract
We survey the problem of detecting isomorphism between two combinatorial structures, such as graphs, matrices and designs. Related to these are the problems of computing automorphism groups and canonical forms. Emphasis will be on the practical aspects of the problem rather than on the theoretical niceties. The author's program "nauty" has been one of the leaders for more than 40 years.
-
Structure generation and approximate counting
Date: Monday 1 July 2019, 14h00
Venue: KU Leuven
Location: Department of Computer Science, Lecture room A05.152, Celestijnenlaan 200A, 3001 Heverlee
Abstract
In this talk we will consider two interconnected topics. One is the constructive enumeration (either exhaustive or random) of a class of discrete structures. Of particular importance is the avoidance of isomorphic copies. The other topic is the approximate determination of the number of objects without generating them. We will explain several theoretical approaches as well as their practical implementation.
-
Computing Ramsey numbers
Date: Tuesday 9 July 2019, 14h00
Venue: Ghent University
Location: Campus Sterre, Building S9, lecture room 3.1, Krijgslaan 281, 9000 Ghent
Abstract
The classical Ramsey number R(s,t) is the smallest n such that, for every colouring of the edges of the complete graph K_n using two colours, there is either an s-clique of the first colour or a t-clique of the second colour. Despite considerable effort by many people over decades, only a handful of classical Ramsey numbers are known exactly. The most recent determination R(4,5)=25 was 24 years ago (McKay and Radziszowski, 1995). Since that time, the most sought number has been R(5,5).
In the first part of the talk we will show a new computational approach that improves the upper bound to R(5,5) to 48 and maybe even to 47.
In the second part of the talk we will show how subgraph identities combined with linear programming can be used to improve the known upper bounds on R(s,t) for many larger values of s and t.
-
The volume of the Birkhoff polytope
Date: Tuesday 6 August 2019, 14h00
Venue: Université Libre de Bruxelles
Location: Campus de la Plaine, NO Building, Solvay Room (5th floor), ULB CP212, Boulevard du Triomphe, 1050 Bruxelles
Abstract
A permutation matrix is a 0-1 matrix with one 1 in each row and in each column. The set B(n) of all n by n matrices of nonnegative real numbers with every row and every column having sum 1 is called the Birkhoff polytope. An easy theorem says that every matrix in the Birkhoff polytope is a nonnegative combination of permutation matrices. In this talk we find the volume of the Birkhoff polytope by using complex analysis in many dimensions to enumerate integer matrices with constant row and column sum and applying the theory of Ehrhart about the number of integer points in a polytope.
Closing symposium
Ghent Graph Theory Workshop
12-14 August 2019
Organisation
Host institution
- Department of Applied Mathematics, Computer Science and Statistics
- Combinatorial algorithms and algorithmic graph theory
Prof. Gunnar Brinkmann and dr. Jan Goedgebeur
- Combinatorial algorithms and algorithmic graph theory
Partner institutions
- University of Mons: prof. Hadrien Mélot
- Université Libre de Bruxelles: prof. Bernard Fortz