IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Some Hypercube Problems and Conjectures

  • April 18, 2014
  • 11 a.m.
  • LeConte 312

Abstract

In this talk we give a short review of some research problems in graph theory. We use hypercube problems and conjectures as examples to explain the ideas. Hypercubes are very interesting objects which arise in many different areas of mathematics. As a graph, a hypercube Q_n is a graph in which the vertices are all binary vectors of length n, and two vertices are adjacent if and only if the Hamming distance between them is 1, i.e. their components differ in one place. Hypercubes have many applications and there are many challenging conjectures about them. Here we discuss some of these conjectures and applications. Our emphasis will be on the star arboricity (or galactic number) and forced matching.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC