Modular and Lexical Matchings in the Middle Levels Graph Open Access

Wingfield, Kevin (2012)

Permanent URL: https://etd.library.emory.edu/concern/etds/s1784m73m?locale=en
Published

Abstract

Abstract
Modular and Lexical Matchings in the Middle Levels Graph
Classes of explicitly defined matchings in the middle levels bipartite graph
induced by the Boolean lattice are investigated. The original motivation for
an investigation into the Hamiltonicity of the middle levels bipartite graph
came from the conjecture of Havel. Here, we collect some known results
and present some new observations that indicate that, when disjoint, the
2-factors obtained from taking the union of pairs of these matchings always
contain short cycles.

Table of Contents

Contents

1 Introduction 1

1.1 Definitions and notation ..................... 4

1.2 Automorphisms in Bk ............................ 6

2 Modular Matchings 7

2.1 Definitions and preliminaries................... 7

2.2 Pairwiseunionsofmodularmatchings. . . . . . . . . . . . . . 10

2.3 3-factors of modular matchings ................. 16

3 Lexical Matchings 20

3.1 Definitions and background results ............... 21

3.2 Partial results........................... 27

4 Future Work 33

Bibliography 35

About this Master's Thesis

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research Field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Thumbnail Title Date Uploaded Actions
Modular and Lexical Matchings in the Middle Levels Graph () 2018-08-28 16:31:39 -0400

Supplemental Files

Thumbnail Title Date Uploaded Actions