# Advances in Discrete Mathematics and its Applications

Mathematics is an exciting growth area of research in the modern information age. It has an inherently interdisciplinary flavour with roots in pure mathematics, and a wide range of applications in networks, algorithms, etc.

Discrete Mathematics is concerned with structures, often finite, that take on discrete values. It is best understood in distinction to Continuous Mathematics, which studies quantities that vary continuously. It is Continuous Mathematics that underlies the motion of the planets or fluids. In contrast, Discrete Mathematics underpins the world of information, both synthetic, such as digital computers and communication networks, and natural, such as DNA sequences. Continuous Mathematics held sway over the 19th and early 20th century, but with the rise of the digital society, Discrete Mathematics has become increasingly important, and that trend continues. Today, Discrete Mathematics is an exciting and rapidly developing area, with roots in Pure Mathematics, most particularly Combinatorics, and a wide range of applications in the modern world. To give just one example, research in Algorithms and Networks, such as that being undertaken at QMUL and Warwick, will be vital to meet future challenges for society, such as reliability of global energy, and efficient communication in the information age.

The collaboration is built on two existing centres of excellence at the two sites:

At Warwick, the Centre for Discrete Mathematics and its Applications (DIMAP) is a collaboration between the Department of Computer Science, the Warwick Mathematics Institute, and the Operational Research and Management Sciences group in the Warwick Business School. It was established in March 2007 by the University of Warwick, partially funded by an EPSRC Science and Innovation Award EP/D063191/1 of £3.8 million.

The Centre for Discrete Mathematics is a new initiative at QMUL that will encourage both mathematical and interdisciplinary approaches to the field, within QMUL, and in collaboration with DIMAP at the University of Warwick. It builds on existing collaborations and joint grants held by members of the School of Mathematics and Department of Computer Science.

Both centres are internationally recognised for their research excellence in discrete mathematics and combinatorics, and their applications in algorithms, networks, and computational complexity, but their strengths are largely complementary. Some of the first things to be asked about a discrete structure are computational: Can we decide efficiently whether one exists satisfying a certain property? What is the optimal structure in some measure? These are questions of Computational Complexity, a branch of Theoretical Computer Science. Although QMUL and Warwick have expertise in both Combinatorics – i.e., “pure Discrete Mathematics” – and Theoretical Computer Science, their strengths are largely complementary. Warwick has the greater concentration in Algorithms and Computational Complexity, while QMUL has the greater concentration in Combinatorics.

Below are two possible areas at the interface of Mathematics and Computer Science that would promote activity between the two institutions.

**i. Algorithmic Complexity and Statistical Mechanics**

Algorithmic Complexity aims at providing understanding of problems arising in Computer Science and designing mathematical tools and better algorithms to solve these problems. The theory also addresses the fundamental question of which problems are computationally tractable and which are intractable. Statistical Mechanics, in contrast, provides a framework for relating the microscopic properties of individual atoms and molecules to the macroscopic bulk properties of materials. Research here has several strands: at QMUL, Tutte polynomials in Graph Theory, exact enumeration for lattice paths and Rigidity; at Warwick, statistical mechanics and phase transitions. On the surface, these two topics – Computational Complexity and Statistical Mechanics – appear unrelated. However, it is becoming apparent that exciting connections exist between the two. Empirically, it appears that computational intractability is related to the existence of phase transitions, but it is a major challenge to formalise this connection.

**ii. Extremal Combinatorics and Network Coding**

Extremal Combinatorics concerns extremal values of a function defined on some class of combinatorial objects. This framework encompasses a broad range of problems, from Network Optimisation in Operations Research to fundamental questions in Discrete Mathematics. It has applications to Additive Number Theory, Coding Theory, and Complexity Theory. It is an area of synergy between QMUL and Warwick with collaborations that would be enhanced and cemented by the link provided by a joint fellow. Network Coding, which studies transmission of information through a network, with extra efficiencies exploiting the digital nature of information. Its theoretical analysis involves natural questions in Extremal Combinatorics and has had industrial impact, as it has been incorporated in Microsoft’s Avalanche file-distribution system.

Informal enquiries may be directed to Prof Artur Czumaj or Prof Peter Keevash.

Further collaboration will be achieved by Summer Schools jointly organised by the two collaborating Universities and the Post Doctoral Research Fellows at both sites, and a series of joint mini-workshops organised alternately in London and in Warwick.