Theses and Dissertations

2018

Document Type

Open Access Dissertation

Mathematics

Sub-Department

College of Arts and Sciences

Linyuan Lu

Abstract

Turán problems on uniform hypergraphs have been actively studied for many decades. However, on non-uniform hypergraphs, these problems are rarely considered. We refer a non-uniform hypergraph as an R-hypergraph where R is the set of cardinalities of all edges. An R-graph H is called degenerate if it has the smallest Turán density |R(H)|−1. What do the degenerate R-graphs look like? For the special case R = {r}, the answer to this question is simple: they are r-partite r-uniform hypergraphs. However, it is more intrigue for the other cases. A degenerate hypergraph is called trivial if it is contained in the blow-up of a single edge or a chain. In this thesis, we characterize the degenerate {1, 3}-hypergraphs, we proved that there always exist non-trivial degenerate R-graphs except the cases R = {r} and R = {1, 2}. We extend our work to the Turán density of k-edge-colored r-uniform hypergraphs. We determine the Turán densities of all 2-edge-colored bipartite graphs, also give an important application of the study of 2-edge-colored graphs on Turán problems of {2, 3}-hypergraphs.

Hypergraphs are simply generalization of graphs. Tensors are simply generalization of matrices. Over the past decade, the spectral theory of hypergraphs and tensors has been developed. Many properties of graphs and matrices have been generalized to hypergraphs and tensors. The second main concern of this thesis is to study the methods for finding the largest eigenvalue of uniform hypergraphs and determining the maximum high-order tensors when fix some parameters. We give a tight upper bound on the spectral radius of an r-uniform hypergraph H with fixed number of edges. Our result generalizes the classical Stanley’s theorem on graphs. We extend

the problem to general r-order {0, 1}-tensor A, we prove that the spectral radius of A with e ones is at most e r−1/r with the equality holds if and only if e = kr for some integer k and all ones forms a principle sub-tensor 1k×k×...k. We also prove a stability result for general tensor A with e ones where e = kr + l with relatively small l. Using the stability result, we completely characterized the maximum tensors among all r-order {0, 1}-tensor A with kr + l ones, for −r <= l <= r + 1, and k sufficiently large. To prove above results, we generalize several important theorems from matrices to tensors.

COinS