Discrete Math Seminar: Kseniya Garaschuk

  • Date: 11/25/2014
  • Time: 16:00
Lecturer(s):
Kseniya Garaschuk, UBC
Location: 

University of British Columbia

Topic: 

Some aspects of rational triangle decompositions

Description: 

Given a simple graph $G$, a triangle decomposition of $G$ is a set of subgraphs isomorphic to $K_3$ whose edges partition the edge set of $G$. Further, a rational triangle decomposition of $G$ is a non-negative rational weighting of the copies of $K_3$ in $G$ such that the total weight on any edge of $G$ equals one. In this thesis, we will explore sufficient conditions for rational triangle decomposability. A famous conjecture in the area due to Nash-Williams states that any sufficiently large graph (satisfying some divisibility conditions) with minimum degree at least $3/4v$ is admits a triangle decomposition; the same conjecture stands for rational triangle decomposability (no divisibility conditions required). By perturbing and restricting the coverage matrix of a complete graph, we show that minimum degree of at least $22/23v$ is sufficient to guarantee that the given graph is rationally triangle decomposable. This density bound is a great improvement over the previously known results and is derived using estimates on the matrix norms and structures originating from association schemes.

Other Information: 

Location: ESB 4127