Mathematical ideas and their innovation rely on, and build upon the wonders in its abstraction. Graph theory studies the mathematical structures in the modelling of pairwise relations between objects. Graph theory, or graphs are well-suited and are convenient tools to represent a collection of interconnected objects in a precise and orderly manner. This practice has been a common practice among researchers to efficiently model and analyse the structure of a network and study their properties.

In graph theory, the term “graph” refers to a set of nodes (called vertices) together with a set of lines (called edges) that connect the nodes. Two vertices of a graph are adjacent if there is an edge joining them. A path is a sequence of vertices such that each vertex in the sequence is adjacent to the vertex next to it. A path with distinct vertices is called a simple path. A graph is connected if there is a path from any vertex to any other vertex in the graph. A complete graph is a simple graph whose vertices are pairwise adjacent. When a connected graph can be drawn on the plane without any edges crossing, it is called a planar graph.

Combinatorics (or combinatorial mathematics) is an important branch of mathematics involving the study of arrangements of objects and finite discrete structures. Counting of objects or their arrangements is an important part of combinatorics. Graph theory is usually studied alongside combinatorics as problems are often confronted in discrete structures related to counting.

In combinatorial mathematics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. It addresses the preservation of properties under set partitions. Ramsey theory for two colours states that, for any positive integers p and q both greater than 2, there exists a least positive integer R (known as Ramsey number) such that every edge-colouring (with colours red and blue) of a complete graph with R vertices, admits either a red complete graph subgraph on p vertices or a blue complete graph subgraph on q vertices. Ramsey theory for two colours can be easily generalized to more than two colours. However, the associated Ramsey numbers are notoriously difficult to compute as the number of colours increases.

The School of Mathematical Sciences is currently working on a research project entitled “On Ramsey-type theorems for integers and other related problems in combinatorics”. The project funded by the Ministry of Higher Education, Malaysia, investigates Ramsey-type theorems on graphs and integers. Ramsey-type theorems have roots in different branches of mathematics and the theory developed from them influenced such diverse areas as number theory, set theory and theoretical computer science. The Ramsey theorem broadens the perspective in cyber security by visualizing the pattern of the network. Much of computer security involves analysing structures or items that are hiding within large, complex systems. Obvious examples include forensic analysis (inferring the source or creator of a piece of malicious code from its form, structure, or coding style) and intrusion detection (locating malicious attack packets within a large stream of network traffic).

For example, network defence analyse the systems (nodes) an attacker can gain access (exploit a connection to) after having compromised one system. By having a clearer pattern of such network, the computer scientists can model pattern matching (think of best responses to a search query term) in terms of parts of pattern (the query) and links (websites).

Researchers could also demonstrate that, when a social or electronic network reaches a certain size, it should be partitioned into several smaller but connected networks, to reduce the probability that some forbidden or unwelcome structure is present in the system.

This project has the potential to enhance research activities in the Pure Sciences in Malaysia via its research outputs and collaboration between researchers in different institutions. Applying the Ramsey-type theorems on graphs and integers could potentially be used in fields such as number theory and theoretical computer sciences are also expected to bring together researchers from different areas.

Dr Sim Kai An 
School of Mathematical Sciences
Email: @email