Combinatorial mathematics, or combinatorics for short, is the study of structures consisting of a finite number of objects. It mainly has three forms: enumerative (counting the number of structures of a given kind), extremal (establishing how small or how large a parameter of a structure can be) and structural (determining properties of a structure). Examples of enumerative results are given in the Did You Know? section. The Sound Bites section provides examples of extremal or structural problems treated by two of the authors (Professors Peter Borg and Irene Sciriha).

Graph theory is a popular area of combinatorics. Here a graph is essentially a network. It simply consists of a set of objects, called vertices, together with a set of pairwise connections called edges. It represents relations, such as social acquaintances, molecular bonds, and town/computer network/ internet connections (links).

One of the most outstanding mathematical results is the Four Colour Theorem, stating that, for any map, it is possible to use at most four colours for giving each region a colour in such a way that no two neighbouring regions receive the same colour. A map has a graph representation; the regions are the vertices, and two vertices are connected by an edge if the two regions are neighbours. Thus, for such a graph, four colours suffice for colouring the vertices in such a way that no two connected vertices are coloured the same.

Combinatorics was introduced to the University of Malta by Prof. Stanley Fiorini in 1975. The authors of this page were all tutored and influenced by him. They currently form the combinatorics research group in the Department of Mathematics within the Faculty of Science and are actively engaged in combinatorial research. Several students are pursuing combinatorics at Masters or PhD level; four of last year’s seven PhD graduates in the Faculty of Science were mathematics students, and they all did their PhD in combinatorics.

The authors organised The Second Malta Conference in Graph Theory and Combinatorics, which was held at the db San Antonio Hotel + Spa, St Paul’s Bay during 26-30 June. This international conference commemorated Prof. Fiorini’s 75th birthday. It saw the participation of 14 foreign plenary speakers, most of whom are of world class status, together with Prof. Fiorini’s PhD supervisor, Prof. Robin Wilson, as a special guest of honour. It brought together almost 200 participants from 46 countries and 115 universities. Many of those present had the opportunity to present their recent research findings. There were 150 contributed talks organised in four parallel sessions spread over the five-day period. A special issue of the prestigious journal Discrete Applied Mathematics will be dedicated to this conference and will contain original research papers authored by participants.

The conference served to promote the mathematical research carried out at the University of Malta and to strengthen the reputation of the Department of Mathematics, the university and the country in international fora.

## Sound bites

• Consider a group of people. Assume that if person A knows person B, then B knows A; this is represented by an edge AB (or BA, the same edge). Let the number of group members a person knows be called the person’s degree. How many people need to be removed from the group so that the maximum degree is less than that of the original group? We want the smallest number; denote it by s. Note that simply removing the members of maximum degree may not be the best solution. This can be viewed as a problem for graphs; in this case, the people are the vertices, and the edges are as above. In a paper published last week in The Australasian Journal of Combinatorics (Volume 69, Part 1), Prof. Peter Borg and his PhD student Kurt Fenech established bounds for s in terms of the number n of vertices, the maximum degree k, and the number t of vertices of maximum degree. They showed that s is at most (n + (k-1) x t) / (2k). This bound is attained by some graphs.

• The idea that atoms could be used to construct nanoscale machines was first raised by Feynman in 1900. The flurry of scientific activity triggered by the discovery of fullerenes and the related Nobel prizes in chemistry and physics in 1996 and 2010, respectively, placed spectral graph theorists in high demand. To enhance the understanding of the electrical activity through a carbon molecule, the carbon atoms and the bonds between pairs of them are represented by a graph. Connecting two atoms of the molecules in a circuit, across a bias voltage, produces a molecular electrical device. The impact of spectral graph theory on molecular conductivity is on a new path after the discovery last year by the spectral graph theory group led by Prof. Irene Sciriha from Malta and the chemists led by Prof. P. W. Fowler from Sheffield University, UK, that electrons flow through molecular orbitals acting as parallel conducting channels between the terminals, rather than through bonds between atoms [The Journal of Chemical Physics 143, 194105 (2015)]. This is leading to predictions in the rapidly expanding area of nanotechnology.

*For more science news, listen to Radio Mocha on Radju Malta 2 every Monday at 1pm and every Friday at 6pm.*

## Did you know?

Let n be a positive whole number. The number of ways of permuting (reordering) the list 1, 2, ..., n is 1 x 2 x ... x n. It is denoted by n! and called the factorial of n. 0! is defined to be 1.

The number of ways of forming a subset of {1, 2, ..., n} with exactly k distinct members (order does not matter) is n! divided by k! x (n-k)!. It is denoted by nCk.

A derangement of 1, 2, ..., n is a permutation of 1, 2, ..., n such that, for each j, j is not in position j (for example, 3, 1, 4, 2 is a derangement of 1, 2, 3, 4). The number of derangements of 1, 2, ..., n is nC0 x n! - nC1 x (n-1)! + nC2 x (n-2)! – ... and is denoted by dn.

As n grows large, n! divided by dn converges to a number e = 2.718281828459... (the number of digits is infinite). Like π, e is irrational (not a whole divided by a whole) and plays a special role in mathematics. It features in important formulas of various disciplines, such as statistics (normal distribution), physics (radioactive decay) and finance (continuous compounding). Euler’s identity eiπ + 1 = 0 (linking the fundamental constants 0, 1, e, π, and the square root i of -1) is widely considered the most beautiful.

Independent journalism costs money. Support Times of Malta for the price of a coffee.

Support Us