Inne Singgih

Date of Award

Spring 2020

Document Type

Open Access Dissertation

Department

Mathematics

First Advisor

Éva Czabarka

Second Advisor

László Székely

Abstract

The first part of this dissertation discussing the problem of bounding the diameter of a graph in terms of its order and minimum degree. The initial problem was solved independently by several authors between 1965 − 1989. They proved that for fixed δ ≥ 2 and large n, diam(G) ≤ 3n+ O(1). In 1989, Erdős, Pach, Pollack, and Tuza conjectured that the upper bound on the diameter can be improved if G does not contain a large complete subgraph Kk.

Let r, δ ≥ 2 be fixed integers and let G be a connected graph with n vertices and minimum degree δ. In general, Erdős et al. conjectured tight upper bounds for K2r -free and K2r+1-free graphs that are better than the known δ+1 + O(1). Particular to this dissertation, their conjecture stated that K5-free graphs with 5 l δ have diameter ≤ 2δ + O(1), while K4-free graphs with 8 l δ have diameter ≤ 7δ + O(1).

The first progress towards this conjecture was published by Czabarka, Dankel- mann, and Székely in 2008. They worked under the stronger assumption for when r = 2, that the graphs are 4-colorable rather than K5-free. They showed that for every connected 4-colorable graph G of order n and δ ≥ 1, diam(G) ≤ 5n − 1.

We provide a counterexample to this 30 years old unsolved conjecture for K4-free graphs by showing classes of 3-colorable graphs with diameter 7n 3δ+3+ O(1). From here we conjectured that 3-colorable graphs has diameter at most 7n + O(1). We use the Duality of Linear Programming to prove 3-colorable graphs have diameter at most 2δ + O(1). We then utilize inclusion-exclusion into a different linear programming approach to prove a smaller upper bound that for every connected 3-colorable graph G of order n and δ ≥ 1, diam(G) ≤ 189n + O (1).

The second part of this dissertation gives some remarks on the midrange crossing constant. The celebrated Crossing Lemma states that for any graph on n vertices and m C 4n edges we have cr(G) n2 m3 is at least 1 64 . A decade before the Crossing Lemma, Erdos and Guy made the bold conjecture that, if we denote by k(n,m) the minimum crossing number of n-vertex graph with at least m = m(n) edges, then there is a positive constant , dubbed as the midrange crossing constant, such that = lim n ∞ ª k(n,m) n2 m3 as long as m is both superlinear in n. Pach, Spencer and Tóth showed that the Erdos-Guy conjecture is true with the additional (and needed) assumption that m is subquadratic. Pach, Radoicic, Tardos and Tóth gave a construction yielding B 8 9 ϖ 2 ≈0.0900633 for the rectilinear midrange crossing constant. Details of neither of these calculations, which are said to be long and unpleasant, are available to the public. We provide a simple alternative construction that yields the same upper bound.

Rights

© 2020, Inne Singgih

Download

Included in

Mathematics Commons

Share

COinS