Department of Mathematics

Indian Institute Of Technology Madras , Chennai
  • Department of Mathematics-Shifted to NAC Office of the Department of Mathematics is moved from HSB to New Academic Complex (NAC) 5th and 6th Floor

Graph Theory General Position Problem with applications

Speaker : Paul Manuel, Kuwait University, Kuwait.

29-08-2018

Abstract :

The no-three-in-line problem is to find the maximum number of points that can be placed in the $n \times n$ grid so that no three points lie on a line. This is a celebrated century-old combinatorial problem in the area of discrete geometry and was originally introduced by Henry Dudeney in 1917. A well- known conjecture is that $2n$ points can be placed with no three in a line for all $n \times n$ grid.
An extended version of no-three-in-line problem in discrete geometry is General Position Subset Selection. For a set $P = \{p_1, p_2 \cdots p_n\}$ of $n$ points in the plane, a subset $S \subseteq P$ is in general position if no three points in $S$ are collinear (that is, lie on the same line). Given a set, $P = \{p_1, p_2 \cdots p_n\}$ of $n$ points in the plane, the discrete geometry general position problem is to find maximum number of vertices $S$ so that no three vertices of $S$ are collinear in the plane. Given a graph $G(V, E)$, the graph theory general position problem is to find the maximum number of vertices $S$ so that no three vertices of $S$ lie on a geodesic (shortest path).
In this seminar, we discuss the historical development of general position problem over the last 100 years. We also study the mathematical features of general position problem and some interesting research problems. The aim of this seminar is to motivate young researchers towards potential research collaboration in this field. The seminar will be accessible to the general audience.

Key Speaker Paul Manuel, Kuwait University, Kuwait.
Place Madhava Hall
Start Time 3:00 PM
Finish Time Not Specified
External Link None