Search

We find the Colin de Verdiere number μ for all complete multipartite graphs and show that for any graph G there exists a reduction process that results in a complete multipartite graph H with μ ( G ) ≤ μ ( H ) . We give examples of the upper bounds that can be obtained via this process.

A small improvement is made to the zero-forcing variants defined by Butler, Grout, and Hall (2015) for matrices with a given number of negative eigenvalues, resulting in a better value for the Barioli-Fallat tree and one negative eigenvalue.

We prove that an n-by-n complex positive semidefinite matrix of rank r whose graph is connected, whose diagonal entries are integers, and whose non-zero off-diagonal entries have modulus at least one, has trace at least n + r − 1.

We define an abstract Apollonian supergasket using the solution set of a certain Diophantine equation, showing that the solutions are in bijective correspondence with the circles of any concrete supergasket. Properties of the solution set translate directly to geometric and algebraic properties of Apollonian gaskets, facilitating their study. In particular, curvatures of individual circles are explored and geometric relationships among multiple circles are given simple algebraic expressions. All results can be applied to a concrete gasket using the curvaturecenter coordinates of its four defining circles. These techniques can also be applied to other types of circle packings and higher-dimensional analogs. An Apollonian gasket is a type of circle packing in the plane generated recursively starting from a set of four mutually tangent circles. The curvatures of any four such circles are related by an equation discovered by Descartes, and every circle in a gasket generated by four circles with integer curvatures will have integer curvature. While these gaskets have been fascinating to mathematicians for some time — the use of group theory in their study was initiated by Keith Hirst [1967] and they even inspired a poem 1 — it was only relatively recently that Jeffrey Lagarias, Colin Mallows, and Allan Wilks [Lagarias et al. 2002] gave an algebraic characterization of Descartes configurations. One question in particular has inspired much work but resisted a complete answer: given the four original integer curvatures, which other curvatures can or will occur, and how frequently? Peter Sarnak [2011], Elena Fuchs [2013], and Hee Oh [2014] have recent surveys on this topic, which has seen significant progress in the past five years [Bourgain 2012; Bourgain and Kontorovich 2014; Bourgain and Fuchs 2011; Fuchs and Sanden 2011]. In this paper, inspired by recent work of Sam Northshield [2015], we provide a four-dimensional label to each circle that does not depend on the location of the circle but refers instead to its geometric relationship to the original four circles. Since we consider only the process of generating the gasket, the labels provide an

We present a method to construct a proper coloring of a graph from a positive semidefinite zero forcing set.

The possible zero/nonzero patterns of unitary matrices are of interest in quantum evolution and the study of quantum systems on graphs. In particular, a quantum random walk can be defined on a directed graph if and only if that graph is associated with a unitary matrix pattern. We propose positive semidefinite zero forcing as a way to determine whether there exists a unitary matrix with a given zero/nonzero pattern. We show that zero forcing is a better criterion than strong quadrangularity of the pattern and prove that an n -by-n pattern supports a unitary matrix if and only if its positive semidefinite zero forcing number equals n for n ≤ 5.

The real (complex) minimum semidefinite rank of a graph is the minimum rank among all real symmetric (complex Hermitian) positive semidefinite matrices that are naturally associated via their zero-nonzero pattern to the given graph. In this paper we give an upper bound on the minimum semidefinite rank of a graph when the graph is modified from the superposition of two graphs by cancelling some number of edges. We also provide a lower bound for the minimum semidefinite rank of a graph determined by a given cutset. When the complement of the cutset is a star forest these lower and upper bounds coincide and we can compute the minimum semidefinite rank in terms of smaller graphs. This result encompasses the previously known case in which the cut set has order two or smaller. Next we provide results for when the cut set has order three. Using these results we provide an example where the positive semidefinite zero forcing number is strictly greater than the maximum positive semidefinite nullity.

We prove that the ordered subgraph number of a connected graph that has no duplicate vertices is at most three if and only if the complement does not contain a cycle on four vertices. The duality between zero forcing and ordered subgraphs then provides a complementary characterization for positive semidefinite zero forcing. We also provide some necessary conditions for when the minimum semidefinite rank can be computed using tree size.

In this note, we combine a number of recent ideas to give new results on the graph complement conjecture for minimum semidefinite rank.

The minimum semidefinite rank (msr) of a graph is defined to be the minimum rank among all positive semidefinite matrices whose zero/nonzero pattern corresponds to that graph. We recall some known facts and present new results, including results concerning the effects of vertex or edge removal from a graph on msr.

In 1980, J. Bourgain and F. Delbaen constructed two classes and of ∞-spaces each exhibiting many surprising properties. In particular, the members of each possess the Schur property and the members of are somewhat reflexive. In this paper, for a Banach space in either of these classes we define a bounded shift-type operator which is an isometry when restricted to a certain hyperplane.

The minimum rank of a graph is the smallest possible rank among all real symmetric matrices with the given graph. The minimum semidefinite rank of a graph is the minimum rank among Hermitian positive semidefinite matrices with the given graph. We explore connections between OS-sets and a lower bound for minimum rank related to zero forcing sets as well as exhibit graphs for which the difference between the minimum semidefinite rank and these lower bounds can be arbitrarily large.

The Colin de Verdi`ere parameters, μ and ν, are defined to be the maximum nullity of certain real symmetric matrices associated with a given graph. In this work, both of these parametersare calculated for all chordal graphs. For ν the calculation is based solely on maximal cliques, while for μ the calculation depends on split subgraphs. For the case of μ our work extends some recent work on computing μ for split graphs.

Let G = (V, E) be a multigraph with no loops on the vertex set V = {1, 2, . . . , n}. Define S+(G) as the set of symmetric positive semidefinite matrices A = [aij ] with aij 6= 0, i 6= j, if ij ∈ E(G) is a single edge and aij = 0, i 6= j, if ij / ∈ E(G). Let M+(G) denote the maximum multiplicity of zero as an eigenvalue of A ∈ S+(G) and mr+(G) = |G|−M+(G) denote the minimum semidefinite rank of G. The tree cover number of a multigraph G, denoted T (G), is the minimum number of vertex disjoint simple trees occurring as induced subgraphs of G that cover all of the vertices of G. The authors present some results on this new graph parameter T (G). In particular, they show that for any outerplanar multigraph G, M+(G) = T (G).

The minimum vector rank (mvr) of a graph over a field F is the smallest d for which a faithful vector representation of G exists in F d . For simple graphs, minimum semidefinite rank (msr) and minimum vector rank differ by exactly the number of isolated vertices. We explore the relationship between msr and mvr for multigraphs and show that a result linking the msr of chordal graphs to clique cover number also holds for the mvr of multigraphs. We study the difference between msr and mvr in the removal of duplicate vertices in multigraphs, and relate mvr to certain coloring problems. A subset of vertices and the set of edges among them in G form an induced subgraph of G. We let N(v) denote the neighborhood of a vertex v, which is the set of vertices of G adjacent to v, and set N(v) = {v} ∪ N(v). We also define N1(v) to be the set of vertices of G adjacent to v by exactly one edge, and set N1(v) = {v} ∪ N1(v). Note that, for a simple graph, N1(v) = N(v) for every vertex v. We say a vertex v is singly-isolated if N1(v) is empty. A square matrix M = (mij) is combinatorially symmetric when mij = 0 if and only if mji = 0. If G is a graph on n vertices that has no loops, let C(G, F) denote the set of all n-by-n combinatorially symmetric matrices with entries in the field F such that

For an undirected simple graph G, the minimum rank among all positive semidefinite matrices with graph G is called the minimum semidefinite rank (msr) of G. In this paper, we show that the msr of a given graph may be determined from the msr of a related bipartite graph. Finding the msr of a given bipartite graph is then shown to be equivalent to determining which digraphs encode the zero/nonzero pattern of a unitary matrix. We provide an algorithm to construct unitary matrices with a certain pattern, and use previous results to give a lower bound for the msr of certain bipartite graphs.

We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex.