3rd annual Mississippi Discrete Mathematics Workshop

Abstract.   It was conjectured by Hoffman-Ostenhof that the edge set of every cubic graph can be decomposed into a spanning tree, a matching, and a family of cycles. We show the conjecture is true for 3-connected cubic graphs on the Torus and Klein-bottle. This is a preliminary report.

Abstract.   In graph theory a tree is a connected cycle free graph X. In metric topology a tree X is a uniquely arcwise connected metric space. The shared idea is the existence of a unique minimal path from x to y, which, moreover, is a subset of the image of all paths from x to y. This idea is in turn captured by the notion of a diamond free meet semi-lattice.
A special case of trees in metric geometry, is an R-tree. A metric space is an R-tree if
  1) Any two distinct points {x, y} are the endpoints of a unique subspace homeomorphic to [0,1], and
  2) The mentioned subspace is isometric to a Euclidean segment.
It is immediate that R-trees are connected, locally path connected, and uniquely arcwise connected. The speaker recently found a new and short proof of a widely cited long paper which establishes the converse: Every metrizable, locally path connected and uniquely arcwise connected space is the underlying space of an R-tree.
Given a starting metric, the challenge is to adjust the metric so that all paths become rectifiable, and without destroying the given topology in the process. The algebraic data of the semi-lattice plays a crucial role in both enabling and controlling the choices needed for the construction.

Abstract.   A version of a result of Erdos and Szekeres states that any sequence of n² - 2n + 2 distinct numbers contains a monotonic subsequence of length n, and this is the smallest number for which this is guaranteed to be true. We prove an analogous result in the context of set partitions. We offer a refinement of this result based on the number of blocks in the set partition. If time permits, we will raise some possibly related questions about some geometric objects associated to permutations and set partitions.

Abstract.   The Seymour conjecture, originally proposed in 1974 by Paul Seymour in relation to the Hajnal-Szemeredi theorem, is an open problem in graph theory and states that the k-th power of a Hamiltonian cycle can be found in a graph G with minimum degree at least        k k+1⋅n, where n is the number of vertices of G.
Even though the conjecture has been proved for sufficiently large n by Komlós et al., no hard limit proof has been found. We present the first such hard-limit proof for all possible n and a slightly weaker bound on the minimum degree:       2k2k-1⋅n.
In addition, we discuss the potential for a polynomial-time algorithm derived from our proof that finds powers of Hamiltonian cycles in graphs with the requisite minimum degree.
This is joint work with Andrew Gardner.

Abstract.   A recent branch of research in affine algebraic geometry has been to try and understand the infinite dimensional algebraic variety structure of the group of polynomial automorphisms of affine n-space. In dimension two, a resolution of the so-called Polydegree Conjecture would provide some answers. In studying this question, Furter introduced a question about univariate polynomials, called the Rigidity Conjecture, which implies the Polydegree Conjecture. Later, Edo and van den Essen showed that this, in turn, is equivalent to a special case of a strong version of the Factorial Conjecture. We distill these questions down to a purely combinatorial question, namely one about certain symmetric polynomials, in the hopes that existing combinatorial techniques can be applied to answer these questions.

Abstract.   The binding number of a graph, bind(G), is the minimum ratio (over all subsets S of the vertex set V(G)) of |N(S)| to |S|, such that S is not empty and N(S) is a proper subset of V(G) (N(S) is the set of all vertices with a neighbor in S). It was conjectured by Woodall that bind(G) > 3/2 implies that G contains a triangle (shown to be true by Ronghua) but the question of what threshold on the binding number implies that G contains a clique of order r is still open. In this talk, we will consider some progress on this open question and the related topic of large independent sets in K_r-free graphs with large minimum degree.

Abstract.   Kuratowski’s theorem implies that a non-directed graph G is outerplanar, or has book thickness 1, if and only if G contains neither K₄-minors nor K_2,3-minors. In that sense, minors of K₄ or K_2,3 are forbidden minimals for G to be book thickness 1. We aim to extend the theorem to directed graphs D by using a directed book embedding and, in the process, found a series of directed graphs called deer that are forbidden minimals for D to be book thickness 1.

Abstract.   We present basic properties of universal covering projections and exploit them in order to develop an algorithm for computing all solvable regular covering projections of a given graph admitting a lift of a given group of automorphisms.

Abstract.   An ordered set has the fixed point property iff each order-preserving self map has a fixed point. The question whether a given finite ordered set has the fixed point property is co-NP-complete. Local consistency algorithms on constraint networks provide a set of polynomial heuristics that, when successful, can answer many special instances of NP-complete problems. In this talk, we will examine results that guarantee that, for certain classes of ordered sets, local consistency algorithms will correctly answer the question whether a given ordered set has a fixed point free order preserving self map. We will then indicate how fixed point results derived from algebraic topology could provide stronger such guarantees.

Abstract.   The Padmakar-Ivan (PI) index is a distance-based topological index and a molecular structure descriptor, which recently has found numerous chemical applications. In this paper, we obtain the upper bounds about PI-indices of k-trees and characterize the extremal graphs, and give the exact values of PI-indices for some classes of k-trees.
This is joint work with Bing Wei.

Abstract.   In 1963, Ringel conjectured that the complete graph on 2m+1 vertices can be decomposed by any tree with m edges. In the mid 1980s, Graham and Häggkvist conjectured more generally that every 2m-regular graph and every m-regular bipartite graph can be decomposed by any tree with m edges. Fink showed in 1994 that for any directed tree T, the directed Cayley graph Cay→(G; S) is T-decomposable if |S| = |E(T)| and S is a minimal generating set of G. Building upon that technique, we present a significantly enlarged family of directed Cayley graphs that are T-decomposable by carefully relaxing the minimality condition on the connection set S using a simple concept from combinatorial group theory. This is joint work with Mari Castle and undergraduate student Evan Moore.

Abstract.   The chromatic number of a digraph is the minimum integer k such that there is a partition of vertices into k parts, such that each part does not have a directed cycle. The dichromatic number of a undirected graph G is the maximum chromatic number over all the orientations of G.
In 1979, Erdős and Neumann-Lara conjectured that if the dichromatic number of a graph is bounded, so is its chromatic number. We prove a fractional version of this conjecture. If the fractional chromatic number of a graph is at least t, then the the fractional version of the dichromatic number of the graph is at least t / (18⋅log t). This bound is best possible up to a constant factor.
It is joint work with Bojan Mohar in Simon Fraser University

Abstract.   To study the properties of graphs that have a given degree sequence is a fundamental problem in graph theory, with a long history. It also extends to modern large scale complex networks, such as social networks, various communication networks, biological networks, and others, if instead of a deterministically given degree sequence one considers the degree distribution. The reason for considering the degree distribution is that it is often the most basic and least expensive type of data that can be obtained about a huge real-life graph, yet it may reveal important characteristics about the network. Among the multitude of graph properties, connectivity (edge- or vertex-connectivity) certainly plays a fundamental role; this is the property on which we focus here. Specifically, we address the following question: what is the smallest integer k, such that a k-edge- or k-vertex-connected graph exists with a given degree sequence or a given degree distribution. This minimum connectivity may become a useful tool in a number of applications, such as network topology design, network reliability and security related issues, VLSI design, etc. The problem of finding a graph with minimum connectivity for a given degree sequence or degree distribution is not completely solved in the literature, although partial results exist. In this talk, we will survey both old and recent results, as well as open questions on this problem. This is joint work with my Ph.D. advisor Andras Farago.