Research Fields: Discrete Mathematics and Optimization
Quick links
I. General Introduction to Combinatorics
We will break the introduction into 5 sections¡G
 What is Combinatorics ?
Combinatorics is equivalently known as Discrete Mathematics. From the very beginning of the study of mathematics, arithmetic and geometry represent the origins of discreteness and continuity. The two concepts intertwined into the wonderful world of mathematics. But since the invention, called the calculus, of Newton, analysis had been at the center of attention for almost three hundred years. Although the origins of various topics of modern day discrete mathematics can be traced back to number theory, algebra, probability and elementary geometry, it still has not reached a state of significance and maturity. It is even limited to the form of recreational puzzles with ocean deep potential waiting to be explored.
Since the beginning of this century however, methods and tools of discrete mathematics have started to gain momentum and been widely applied and developed in the scientific community. Gradually, discrete mathematics became a new focus and was regarded a discipline of its own. Some related research fields have started to gather under the umbrella of discrete mathematics (combinatorics). Especially after the 30's, the science of computation has gained revolutionary development both in theory and practicality. Digital computer, a powerful data processing machine, has propelled human civilization to a whole new dimension. It not only facilitates daily lives but also deeply influences our mindset and advancement of human knowledge. Computer operates discretely; it reformulates classical continuous mathematical models into discrete ones which have become significant discrete problems of their own. All of this further establishes the significance of discrete mathematics. Moreover, the enormous processing power of the computer on finite quantities and structures has opened up a whole new frontier and brought in new meanings and challenges.
 What does Combinatorics include ?
Combinatorics is a general term which includes a number of areas, a few of the major areas are :
 Classical counting problems include combinatorial problems on finite collection of sets;
 The construction of combinatorial structures based on Algebra and Topological methods;
 Design Theory based on Group Theory and Finite Geometry;
 Graph Theory, Network, and Theory of Hypergraphs;
 Optimization, Operational Research, and Game Theory;
 Coding Theory and Cryptography;
 Matroid and generalized Greedoid Theory;
 Discrete and Arithmetic Geometry;
 Design and analysis of the principle of Algorithm.
 What are the applications of Combinatorics ?
The largest application is in Computer Science in which Combinatorics is a required course. All digitized products like laser disc, compact disc, mobile phones, satellite communication etc. depend on error correcting code to increase their reliability; ATM card, credit card depend on cryptography; without which daily life will be halted. Furthermore, genetic sequencing problem, option analysis, the stability and food chain, experiment design, are some of the common applications of Combinatorics. Predictably, the demand for combinatorics by non mathematics disciplines will substantially increase. Some even advocate that combinatorics should replace calculus as the fundamental mathematics course for freshmen.
 The Department and Combinatorics :
Our department has the highest number of faculties, among Taiwan universities, in combinatorics covering all major areas of combinatorial research; among the faculty, Honorary Professor Frank Hwang is a world renowned expert in combinatorics.
 Professor Frank Hwang(Specialty: Combinatorial Optimization, Operational Research, Network Design)
 Professor Fu, HungLin(Specialty: Graph Theory, Combinatorial Design)
 Professor Huang, TaYuan(Specialty: Algebraic Combinatorics, Finite Geometry)
 Professor Weng, ChihWen(Specialty: Algebraic Combinatorics, Matrix Theory)
 Professor Chen, ChiuYuan(Specialty: Algorithm, Graph Theory, Discrete Mathematics)
 Assistant Professor Michael Fuchs(Specialty: Metric Number Theory, Analysis of Algorithms)
All courses offered in previous years are listed below. Graduate level courses are generally offered to graduate students once in two years to allow a wider exposure in their twoyear M.S. program :
 Discrete Mathematics I (Undergraduate Required Course)
 Discrete Mathematics II (Undergraduate)
 Coding Theory (Undergraduate & Graduate)
 Combinatorial Coding (Graduate)
 Cryptography (Undergraduate & Graduate)
 Topics in Discrete Mathematics (Graduate Required Course)
 Graph Theory I & II (Graduate Required Courses)
 Design Theory (Graduate)
 Algebraic Combinatorics (Graduate)
 Algebraic Graph Theory (Graduate)
 Probability Graph Theory (Graduate)
 Algorithm (Undergraduate & Graduate)
 Graph Theory Algorithm (Undergraduate & Graduate)
 Analysis of Algorithms (Graduate)
 Combinatorial Optimization (Undergraduate & Graduate)
 Connected Networks (Graduate)
 Group Testing Theory (Graduate)
 Optimal Partition (Graduate)
Combinatorics division is one of the two graduate divisions of our department. The annual intake has increased over the year from five to the current thirteen. PhD degree intake is flexible. Our department has graduated over thirty highly acclaimed PhDs establishing their careers in major local universities.
Top  Connection to Other Departments of NCTU :
Combinatorics related courses offered by other departments in NCTU are as follows:
 Discrete Mathematics
(Department of Electrical and Control EngineeringUndergraduate, Department of Computer Science and Information EngineeringUndergraduate, Department of Computer ScienceUndergraduate)  Combinatorics
(Department of Computer ScienceUndergraduate)  Operational Research
(Institute of Information Management, Department of Management ScienceUndergraduate, Department of Transportation Technology and ManagementUndergraduate, Department of Industrial Engineering and ManagementUndergraduate)  Linear Programming
(Department of Computer Science and Information EngineeringUndergraduate)  Graph Theory
(Department of Computer Science and Information EngineeringGraduate, Department of Computer ScienceGraduate/Undergraduate)  Connected Network
(Department of Computer Science and Information EngineeringGraduate, Department of Computer ScienceGraduate)  Cryptographic Methods
(Department of Computer Science and Information EngineeringGraduate, Department of Computer ScienceGraduate)  Introduction to Cryptography
(Department of Computer Science and Information EngineeringGraduate, Department of Computer ScienceGraduate)  Advanced Cryptography
(Department of Computer ScienceGraduate)  Channel Coding
(Department of Electronics EngineeringGraduate/Undergraduate)  Coding Theory
(Department of Communication EngineeringGraduate/Undergraduate)  Information Theory
(Department of Communication EngineeringGraduate)  Algorithm
(Department of Computer Science and Information EngineeringGraduate/Undergraduate, Department of Computer ScienceGraduate)  Introduction to Algorithm
(Department of Computer Science and Information EngineeringUndergraduate)  Algorithm and Structure
(Department of Computer Science and Information EngineeringGraduate/Undergraduate)  Distributed Algorithm
(Department of Computer Science and Information EngineeringGraduate, Department of Computer ScienceGraduate)  Genetic Algorithm
(Department of Compute ScienceGraduate)
 Discrete Mathematics
II. Research Interests:
Professor Tayuan Huang(Algebraic Combinatorics, Finite Geometry)
The structure of Ppolynomial association schemes is a class of combinatorial structures originated from experimental designs in statistics, which have the properties of high regularity and symmetry. It has close relationship with groups, orthogonal polynomials, lattices, metric spaces, codes and combinatorial designs nowadays.
These structures also appear in algebraic combinatorics as distance regular graphs. My research interests are mainly those high regularity and symmetric property associated with distance regular graphs, including
 finite geometry ¡V geometric constraints
 intersection arrays  combinatorial constraints
 spectra ¡V linear algebraic constraints
 Bose mesner algebras ¡V algebra constraints
The notion of symmetric spin models was first introduced by Jones, and Kauffman around 19841989 for dealing with polynomial invariants of knots, and they were soon generalized to twoweight, fourweight spin models respectively. Possible explicit relationship between fourweight spin models and BoseMesner algebras are also interesting to us.
The current focus of interests is the possible roles played by the structure of distance regular graphs and association schemes in pooling designs of various models.
Top
Professor HungLin Fu (Combinatorial Design, Graph Theory and their Applications)
My recent research includes the following topics:

Top
Professor Chiuyuan Chen(Graph Theory, Computer Algorithms, Interconnection Networks and Wireless Networks)
Recent Research Projects (1)The application of graph theory to the localization and routing problems in wireless sensor networks 
Professor ChihWen Weng (DistanceRegular Graphs, Group Testings, Presentation and Representation Theory, Combinatorial Matrix Theory, Graph Theory)
Yupei Huang, Yehjong Pan and Chihwen Weng, Nonexistence of a Class of DistanceRegular Graphs, the electronic journal of combinatorics, Volume 22, Issue 2 (2015), #P2.37 Jun Guo, Kaishun Wang, Chihwen Weng, Pooling semilattices and nonadaptive pooling designs, Discrete Mathematics 320(2014), 6472 Chiaan Liu, Chihwen Weng, Spectral radius of bipartite graphs, Linear Algebra and its Applications, 474(2015), 30¡V43 YenJen Cheng, Fenglei Fan, Chihwen Weng, An extending result on spectral radius of bipartite graphs, arXiv:1509.07586 
Professor Michael Fuchs (Analytic Combinatorics, Discrete Probability Theory, Analysis of Algorithms, Mathematical Biology, Metric Number Theory)
My research work is concerned with several areas in Discrete Mathematics such as Combinatorics, Discrete Probability Theory and Number Theory. Most of the problems I worked on in recent years arose either from Theoretical Computer Science or Biology (for two figures concerning an area in Algorithms and Data Structures I worked on over the last couple of years see below). A practical problem must normally have at least two of the following three flavors in order that it sparks my interest: (i) combinatorial, (ii) probabilistic, or (iii) analytical. On the theoretical side, I am interested in counting problems in Combinatorics and Metric Diophantine approximation. 
Research Summary in Combinatorics Group of NCTU
 DistanceRegular Graphs: The classification of distanceregular graphs by their spectrums, intersection numbers or other algebraic properties and combinatorial properties. Study other algebraic or combinatorial subjects related to distanceregular graphs, e.g. bent functions, spin models, bidiagonal pairs, quantum algebra.
 Combinatorial Designs related to Group Testing: The construction of pooling designs via graph decompositions and poset structures from finite geometries. The relations between different pooling designs, e.g. the relation between dseparable and ddisjunct matrices.
 Networks: The construction of networks by combinatorial method and algebraic method. The network properties related to general graph theory and number theory, e.g. graph coloring, graph connectivity, Euclidean division algorithm. The network properties related to geometrical properties, e.g. Lshape in Euclidean plane. The behavior of a particular network.
 General Graph Theory: The study of vertex coloring, edge coloring, graph labeling, planar graphs, Hamiltonian paths or cycles, and other related graph properties.