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.

We study how three conjectures concerning Colin de Verdiere’s graph invariant $$\mu $$ behave under joins of graphs. We show that if the component graphs satisfy one of the conjectures, then so does their join under a condition on their optimal vector representations.

We answer a question of Brown and Jordon (2021) [4] by proving the existence of signed Langford sequences of every possible order for each defect. Our proof is constructive, and the constructions are shown to have other interesting properties and connections to several conjectures concerning permutations and partial sums of sequences of elements from cyclic groups.

An n -satisfactory coloring of the n -smooth integers is an assignment of n colors to the positive integers whose prime factors are at most n so that for each such m , the integers m , 2 m , … , n m receive different colors. In this note, we give a short proof that infinitely many 6-satisfactory colorings of the 6-smooth integers exist and show how the technique of the proof can be applied more generally, including for n ∈ { 8 , 10 , 12 } .

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.

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 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.

We prove that a $k$-tree can be viewed as a subgraph of a special type of $(k+1)$-tree that corresponds to a stacked polytope and that these "stacked'' $(k+1)$-trees admit representations by orthogonal spheres in $\mathbb{R}^{k+1}$. As a result, we derive lower bounds for Colin de Verdière's $\mu$ of complements of partial $k$-trees and prove that $\mu(G) + \mu(\overline{G}) \geq |G| - 2$ for all chordal $G$.

We determine those permutations that have maximal absolute total displacement on a finite subset of real numbers, and give some corollaries.

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.