arXiv research

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…

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…

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

Developed a new homology theory for graph chromatic polynomials.

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 …

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 …

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…

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.

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…

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…

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 …

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

Topology helps estimate chromatic numbers of random graphs on spheres.

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…

The goal of this paper is to address A. Shumakovitch's conjecture about the existence of $\Z_2$-torsion in Khovanov link homology. We analyze torsion in Khovanov homology of semi-adequate links via chromatic cohomology for graphs which provides a link between the link homology and well-developed theory of Hochschild ho…

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…

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…

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…

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 …

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…

Chromatic Learning reduces feature dimensions for sparse datasets.

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 …

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 …

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…

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

New framework relaxes independence assumption for graph-mixing dependencies.

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…

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…

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…

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.

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…

The elliptic Hall algebra governs torus link homology.

New framework links fractal complexity to separation dimension.

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…

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

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

Study invariants of null-homologous knots in thickened surfaces.

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.

In the present paper we calculate the Gromov-Hausdorff distance between an arbitrary simplex (a metric space all whose non-zero distances are the same) and a finite metric space whose non-zero distances take two distinct values (so-called $2$-distance spaces). As a corollary, a complete solution to generalized Borsuk p…

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…

Pac-Bayes bounds are among the most accurate generalization bounds for classifiers learned from independently and identically distributed (IID) data, and it is particularly so for margin classifiers: there have been recent contributions showing how practical these bounds can be either to perform model selection (Ambrol…

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…

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…

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