Undecidability of linear inequalities in densities of systems of linear forms - COMP 396 Undergraduate Research Project Application Form

Supervisor's Name: Hamed Hatami

Supervisor's Email: hatami [at] cs.mcgill.ca

Supervisor's Phone: 5147461635

Supervisor's Website: http://www.cs.mcgill.ca/~hatami/

Supervisor's department: Computer Science

Course number: COMP 396 (Computer Science)

Term: Fall 2014-2015

Project start date: 02/09/2014

Project end date: 01/12/2014

Project title: Undecidability of linear inequalities in densities of systems of linear forms

Project description (50-100 words suggested): Many results in extremal combinatorics can be formulated as inequalities between densities of small substructures in large combinatorial structures. One particular class of such inequalities that are of interest to combinatorial number theorists concern  densities of linear structures in subsets of Abelien groups.  We propose to investigate the following question:
Is it undecidable to determine the validity of such an inequality?
In the context of graph theory, Hatami and Norin have recently established the undecidablity of this problem, but in the context of systems of linear forms, the answer is still not known.

Prerequisite: 1 term completed at McGill + CGPA of 3.0 or higher; or permission of instructor.

Grading scheme (The final report must be worth at least 50% of final grade): Weekly meetings (40%), final written report (50%), and an oral presentation (10%)

Project status: This project is taken; however students may contact the professor to discuss other possible '396' projects this term.

Ethics, safety, and training: Supervisors are responsible for the ethics and safety compliance of undergraduate students. This project involves NEITHER animal subjects, nor human subjects, nor biohazardous substances, nor radioactive materials, nor handling chemicals, nor using lasers.