Date of Award

2016

Document Type

Open Access Dissertation

Department

Mathematics

Sub-Department

College of Arts and Sciences

First Advisor

Linyuan Lu

Abstract

We present results in three different arenas of discrete mathematics. Let La(n, H) denote the cardinality of the largest family on the Boolean lattice that does not contain H as a subposet. Denote π(H) := limn→∞ La(n,H) (bn/ n2c) . A crown O2k for k ≥ 2 is a poset on 2 levels whose Hasse diagram is a cycle. Griggs and Lu (2009) showed π(O4k) = 1 for k ≥ 2. Lu (2014) proved π(O2k) = 1 for odd k ≥ 7. We prove that the maximum size of a O6 -free family, when restricted to the middle two levels of Bn, is no greater than 1.56(bn/ n2c). This section is joint work with Linyuan Lu.

The diffusion state distance (DSD) was introduced by Cao-Zhang-Park-DanielsCrovella-Cowen-Hescott (2013) to capture functional similarity in protein-protein interaction networks. They proved the convergence of DSD for non-bipartite graphs. We extend the DSD to bipartite graphs using lazy-random walks and consider the general L q-version of DSD. We discovered the connection between the DSD Lq-distance and Green’s function, which was studied by Chung and Yau (2000). Based on that, we computed the DSD Lq-distance for Paths, Cycles, Hypercubes, as well as random graphs G(n, p) and G(w1, . . . , wn). We also examined the DSD distances of two biological networks. This section is joint work with Peter Chin, Linyuan Lu, and Amit Sinha

Motivated by the recent work on the Turán problems on non-uniform hypergraphs, we study when a fixed non-uniform hypergraph H occurs in random hypergraphs with high probability. To be more precise, for a given set of positive integers R := {k1, k2, . . . , kr} and probabilities p = (p1, p2, . . . , pr) ∈ [0, 1]r, let GR(n, p) be the random hypergraph G on n vertices so that for 1 ≤ i ≤ r each ki-subset of vertices appears as an edge of G with probability pi independently. We ask for what probability vector p, GR(n, p) almost surely contains a given subhypergraph H. Note that the Erdős-Rényi model G(n, p) is the special case of GR(n, p) with R = {2}. The question of the threshold of the occurence of a fixed graph H in G(n, p) is well-studied in the literature. We generalize these results to non-uniform hypergraphs. Surprisingly, those p for which GR(n, p) almost surely contains H, form a convex region (depending on H) in a log-scale drawing. We also consider the associated extension problems. This section is joint work with Linyuan Lu.

Rights

© 2016, Edward Lawrence Boehnlein

Download

Included in

Mathematics Commons

Share

COinS