arXiv research

We study the connections between link invariants, the chromatic polynomial, geometric representations of models of statistical mechanics, and their common underlying algebraic structure. We establish a relation between several algebras and their associated combinatorial and topological quantities. In particular, we def…

The paper reveals a property of chromatic homology for complete graphs.

Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov h…

This paper introduces a conceptual framework, in the context of quantum topology and the algebras underlying it, for analyzing relations obeyed by the chromatic polynomial χ(Q) of planar graphs. Using it we give new proofs and substantially extend a number of classical results concerning the combinatorics of the chroma…

Developed a new homology theory for graph chromatic polynomials.

In this paper we prove the knight move theorem for the chromatic graph cohomologies with rational coefficients introduced by L. Helme-Guizon and Y. Rong. Namely, for a connected graph G with n vertices the only non-trivial cohomology groups $H^{i,n-i}(G)$, $H^{i,n-i-1}(G)$ come in isomorphic pairs: $H^{i,n-i}(G)\cong H…

For each graph we construct graded cohomology groups whose graded Euler characteristic is the chromatic polynomial of the graph. We show the cohomology groups satisfy a long exact sequence which corresponds to the well-known deletion-contraction rule. This work is motivated by Khovanov's work on categorification of the…

In this paper we give a new characterization of the h-vector of the chromatic polynomial of a graph. We introduce reduced chromatic cohomology of a graph and show that h_i are its Betti numbers. We then discuss various combinatorial properties of these cohomologies. In particular we prove that these cohomologies depend…

In the first few homological gradings, there is an isomorphism between the Khovanov homology of a link and the categorification of the chromatic polynomial of a graph related to the link. In this article, we show that the categorification of the chromatic polynomial only contains torsion of order two, and hence Khovano…

This paper defines girth for knots and links, linking it to Khovanov homology.

The Stanley chromatic symmetric function $X_G$ of a graph $G$ is a symmetric function generalization of the chromatic polynomial, and has interesting combinatorial properties. We apply the ideas of Khovanov homology to construct a homology of graded $S_n$-modules, whose graded Frobenius series $Frob_G(q,t)$ reduces to …

Khovanov homology of a link and chromatic graph homology are known to be isomorphic in a range of homological gradings that depend on the girth of a graph. We discuss patterns shared by these two homology theories. In particular, we improve the bounds for the homological span of chromatic homology by Helme-Guizon, Przy…

The paper categorifies matroid characteristic polynomials using cohomology.

We establish a quadratic identity for the Yamada polynomial of ribbon cubic graphs in 3-space, extending the Tutte golden identity for planar cubic graphs. An application is given to the structure of the flow polynomial of cubic graphs at zero. The golden identity for the flow polynomial is conjectured to characterize …

The SO(3) Kauffman polynomial and the chromatic polynomial of planar graphs are categorified by a unique extension of the Khovanov homology framework. Many structural observations and computations of homologies of knots and spin networks are included.

The Penrose-Kauffman polynomial connects knot theory to graph coloring.

This note is dedicated to the study of a Hopf module structures on the space of framed chord diagrams and framed graphs. We also introduce a framed version of the chromatic polynomial and propose two methods to construct framed weight systems.

For each commutative, graded algebra with finite dimension in each degree, we construct a graded cohomology theory for graphs whose graded Euler characteristic is the chromatic polynomial of the graph. This extends our previous work which was based on the algebra $\mathbb {Z}[x]/(x^2)$.

Aguiar and Ardila defined the Hopf monoid GP of generalized permutahedra and showed that it contains many submonoids that correspond to combinatorial objects. They also give a basic polynomial invariant of generalized permutahedra, which then specializes to the submonoids. We define the Hopf monoid of directed graphs a…

This article is about chromatic numbers of hyperbolic surfaces. For a metric space, the $d$-chromatic number is the minimum number of colors needed to color the points of the space so that any two points at distance $d$ are of a different color. We prove upper bounds on the $d$-chromatic number of any hyperbolic surfac…

Higher chromatic numbers $χ_s$ of simplicial complexes naturally generalize the chromatic number $χ_1$ of a graph. In any fixed dimension $d$, the $s$-chromatic number $χ_s$ of $d$-complexes can become arbitrarily large for $s\leq\lceil d/2\rceil$ [6,18]. In contrast, $χ_{d+1}=1$, and only little is known on $χ_s$ for …

The paper defines new TQFTs from non-semisimple categories and proves spherical categories are chromatic.

The chromatic number of sphere graphs in 3-manifolds is bounded.

Let $Δ$ be a trivial knot in the three-sphere. For every finite cyclic group $G$ of odd order, we construct a $G$-equivariant Khovanov homology with coefficients in the filed $\F_{2}$. This homology is an invariant of links up to isotopy in $(S^{3},Δ)$. Another interpretation is given using the categorification of the …

Topology helps estimate chromatic numbers of random graphs on spheres.

In this paper we show that the matrix of chromatic joins and the Gram matrix of the Temperley-Lieb algebra are similar (after rescaling), with the change of basis given by diagonal matrices.

We consider time-domain digital backpropagation with chromatic dispersion filters jointly optimized and quantized using machine-learning techniques. Compared to the baseline implementations, we show improved BER performance and >40% power dissipation reductions in 28-nm CMOS.

We study the chromatic number of the curve graph of a surface. We show that the chromatic number grows like k log k for the graph of separating curves on a surface of Euler characteristic -k. We also show that the graph of curves that represent a fixed non-zero homology class is uniquely t-colorable, where t denotes it…

For every orientable surface of finite negative Euler characteristic, we find a right-angled Artin group of cohomological dimension two which does not embed into the associated mapping class group. For a right-angled Artin group on a graph $\gam$ to embed into the mapping class group of a surface $S$, we show that the …

Motivated by the work in [15], this paper deals with the theory of the braids from chromatic configuration spaces. This kind of braids possess the property that some strings of each braid may intersect together and can also be untangled, so they are quite different from the ordinary braids in the sense of Artin. This e…

The relative chromatic number $c\_0(S)$ of a compact surface $S$ with boundary is defined as the supremum of the chromatic numbers of graphs embedded in $S$ with all vertices on $\partial S$. This topological invariant was introduced for the study of the multiplicity of the first Steklov eigenvalue of $S$. In this arti…

Defines a new 2+1-G-HQFT using graded skein modules.

We introduce characteristics into chromatic homotopy theory. This parallels the prime characteristics in number theory as well as in our earlier work on structured ring spectra and unoriented bordism theory. Here, the K(n)-local Hopkins-Miller classes $ζ_n$ take the places of the prime numbers, and this allows us to di…

Chromatic Learning reduces feature dimensions for sparse datasets.

A 2-complex requires at least 12 colours to avoid edge conflicts.

The algebra of truncated polynomials A_m=Z[x]/(x^m) plays an important role in the theory of Khovanov and Khovanov-Rozansky homology of links. We have demonstrated that Hochschild homology is closely related to Khovanov homology via comultiplication free graph cohomology. It is not difficult to compute Hochschild homol…

Paper connects two invariants of 3D manifolds using Hopf algebras.

J. Przytycki has established a connection between the Hochschild homology of an algebra $A$ and the chromatic graph homology of a polygon graph with coefficients in $A$. In general the chromatic graph homology is not defined in the case where the coefficient ring is a non-commutative algebra. In this paper we define a …

New framework links fractal complexity to separation dimension.

We say a graph has property $\mathcal{P}_{g,p}$ when it is an induced subgraph of the curve graph of a surface of genus $g$ with $p$ punctures. Two well-known graph invariants, the chromatic and clique numbers, can provide obstructions to $\mathcal{P}_{g,p}$. We introduce a new invariant of a graph, the 'nested complex…

New framework relaxes independence assumption for graph-mixing dependencies.

We construct an embedding of any right-angled Artin group $G(Δ)$ defined by a graph $Δ$ into a graph braid group. The number of strands required for the braid group is equal to the chromatic number of $Δ$. This construction yields an example of a hyperbolic surface subgroup embedded in a two strand planar graph braid g…

Higher dimensional graphs can be used to colour two-dimensional geometric graphs. If G the boundary of a three dimensional graph H for example, we can refine the interior until it is colourable with 4 colours. The later goal is achieved if all interior edge degrees are even. Using a refinement process which cuts the in…

We show that in any right-angled Artin group whose defining graph has chromatic number $k$, every non-trivial element has stable commutator length at least $1/(6k)$. Secondly, if the defining graph does not contain triangles, then every non-trivial element has stable commutator length at least $1/20$. These results are…

We study the Orchard relation for generic configurations of points in the plane (also called order types). We introduce infinitesimally-close points and analyse the relation of this notion with the Orchard relation. The second part of the paper deals with monochromatic configurations (for the Orchard relation). We give…

We introduce a novel approach for parallelizing MCMC inference in models with spatially determined conditional independence relationships, for which existing techniques exploiting graphical model structure are not applicable. Our approach is motivated by a model of seismic events and signals, where events detected in d…

We prove several results about the multiplicity of the first Steklov eigenvalues on compact surfaces with boundary. We improve some bounds on the multiplicity, especially for the first eigenvalue, and we prove they are sharp on some surfaces of small genus. In a previous article, we defined a new chromatic invariant of…

We study colorings of the hyperbolic plane, analogously to the Hadwiger-Nelson problem for the Euclidean plane. The idea is to color points using the minimum number of colors such that no two points at distance exactly $d$ are of the same color. The problem depends on $d$ and, following a strategy of Kloeckner, we show…