An official website of the United States government
Abstract Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $$\Delta $$ , then for every integer $$k \geq \Delta +1$$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $$1$$ ; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $$\Delta $$ , then for each $$k \geq \Delta + 1$$ , G has a Borel proper k -colouring in which every two colour classes are related by an element of the Borel full semigroup of G . In particular, such colourings are equitable with respect to every G -invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $$\Delta $$ -colourings of graphs with small average degree. Namely, we prove that if $$\Delta \geq 3$$ , G does not contain a clique on $$\Delta + 1$$ vertices and $$\mu $$ is an atomless G -invariant probability measure such that the average degree of G with respect to $$\mu $$ is at most $$\Delta /5$$ , then G has a $$\mu $$ -equitable $$\Delta $$ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.
more »
« less
Graphs that are cospectral for the distance Laplacian
The distance matrix $$\mathcal{D}(G)$$ of a graph $$G$$ is the matrix containing the pairwise distances between vertices, and the distance Laplacian matrix is $$\mathcal{D}^L (G)=T(G)-\mathcal{D} (G)$$, where $T(G)$ is the diagonal matrix of row sums of $$\mathcal{D}(G)$$. Several general methods are established for producing $$\mathcal{D}^L$$-cospectral graphs that can be used to construct infinite families. Examples are provided to show that various properties are not preserved by $$\mathcal{D}^L$$-cospectrality, including examples of $$\mathcal{D}^L$$-cospectral strongly regular and circulant graphs. It is established that the absolute values of coefficients of the distance Laplacian characteristic polynomial are decreasing, i.e., $$|\delta^L_{1}|\geq \cdots \geq |\delta^L_{n}|$$, where $$\delta^L_{k}$$ is the coefficient of $x^k$.
more »
« less
- PAR ID:
- 10210392
- Date Published:
- Journal Name:
- The Electronic Journal of Linear Algebra
- Volume:
- 36
- Issue:
- 36
- ISSN:
- 1081-3810
- Page Range / eLocation ID:
- 334 to 351
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. In this paper, we consider the family of graphs which contain no $$K_{s,t}$$-minor. We show that for any $$t\geq s \geq 2$$ and sufficiently large $$n$$, there is an integer $$\xi_{t}$$ such that the extremal $$n$$-vertex $$K_{s,t}$$-minor-free graph attaining the maximum spread is the graph obtained by joining a graph $$L$$ on $(s-1)$ vertices to the disjoint union of $$\lfloor \frac{2n+\xi_{t}}{3t}\rfloor$$ copies of $$K_t$$ and $$n-s+1 - t\lfloor \frac{2n+\xi_t}{3t}\rfloor$$ isolated vertices. Furthermore, we give an explicit formula for $$\xi_{t}$$ and an explicit description for the graph $$L$$ for $$t \geq \frac32(s-3) +\frac{4}{s-1}$$.more » « less
-
Abstract The positive Grassmannian $$Gr^{\geq 0}_{k,n}$$ is a cell complex consisting of all points in the real Grassmannian whose Plücker coordinates are non-negative. In this paper we consider the image of the positive Grassmannian and its positroid cells under two different maps: the moment map$$\mu $$ onto the hypersimplex [ 31] and the amplituhedron map$$\tilde{Z}$$ onto the amplituhedron [ 6]. For either map, we define a positroid dissection to be a collection of images of positroid cells that are disjoint and cover a dense subset of the image. Positroid dissections of the hypersimplex are of interest because they include many matroid subdivisions; meanwhile, positroid dissections of the amplituhedron can be used to calculate the amplituhedron’s ‘volume’, which in turn computes scattering amplitudes in $$\mathcal{N}=4$$ super Yang-Mills. We define a map we call T-duality from cells of $$Gr^{\geq 0}_{k+1,n}$$ to cells of $$Gr^{\geq 0}_{k,n}$$ and conjecture that it induces a bijection from positroid dissections of the hypersimplex $$\Delta _{k+1,n}$$ to positroid dissections of the amplituhedron $$\mathcal{A}_{n,k,2}$$; we prove this conjecture for the (infinite) class of BCFW dissections. We note that T-duality is particularly striking because the hypersimplex is an $(n-1)$-dimensional polytope while the amplituhedron $$\mathcal{A}_{n,k,2}$$ is a $2k$-dimensional non-polytopal subset of the Grassmannian $$Gr_{k,k+2}$$. Moreover, we prove that the positive tropical Grassmannian is the secondary fan for the regular positroid subdivisions of the hypersimplex, and prove that a matroid polytope is a positroid polytope if and only if all 2D faces are positroid polytopes. Finally, toward the goal of generalizing T-duality for higher $$m$$, we define the momentum amplituhedron for any even $$m$$.more » « less
-
Abstract Using the invariant theory of arc spaces, we find minimal strong generating sets for certain cosets of affine vertex algebras inside free field algebras that are related to classical Howe duality. These results have several applications. First, for any vertex algebra $${{\mathcal {V}}}$$, we have a surjective homomorphism of differential algebras $$\mathbb {C}[J_{\infty }(X_{{{\mathcal {V}}}})] \rightarrow \text {gr}^{F}({{\mathcal {V}}})$$; equivalently, the singular support of $${{\mathcal {V}}}$$ is a closed subscheme of the arc space of the associated scheme $$X_{{{\mathcal {V}}}}$$. We give many new examples of classically free vertex algebras (i.e., this map is an isomorphism), including $$L_{k}({{\mathfrak {s}}}{{\mathfrak {p}}}_{2n})$$ for all positive integers $$n$$ and $$k$$. We also give new examples where the kernel of this map is nontrivial but is finitely generated as a differential ideal. Next, we prove a coset realization of the subregular $${{\mathcal {W}}}$$-algebra of $${{\mathfrak {s}}}{{\mathfrak {l}}}_{n}$$ at a critical level that was previously conjectured by Creutzig, Gao, and the 1st author. Finally, we give some new level-rank dualities involving affine vertex superalgebras.more » « less
-
Abstract We prove an inequality that unifies previous works of the authors on the properties of the Radon transform on convex bodies including an extension of the Busemann–Petty problem and a slicing inequality for arbitrary functions. Let $$K$$ and $$L$$ be star bodies in $${\mathbb R}^n,$$ let $0<k<n$ be an integer, and let $f,g$ be non-negative continuous functions on $$K$$ and $$L$$, respectively, so that $$\|g\|_\infty =g(0)=1.$$ Then $$\begin{align*} & \frac{\int_Kf}{\left(\int_L g\right)^{\frac{n-k}n}|K|^{\frac kn}} \le \frac n{n-k} \left(d_{\textrm{ovr}}(K,\mathcal{B}\mathcal{P}_k^n)\right)^k \max_{H} \frac{\int_{K\cap H} f}{\int_{L\cap H} g}, \end{align*}$$where $|K|$ stands for volume of proper dimension, $$C$$ is an absolute constant, the maximum is taken over all $(n-k)$-dimensional subspaces of $${\mathbb R}^n,$$ and $$d_{\textrm{ovr}}(K,\mathcal{B}\mathcal{P}_k^n)$$ is the outer volume ratio distance from $$K$$ to the class of generalized $$k$$-intersection bodies in $${\mathbb R}^n.$$ Another consequence of this result is a mean value inequality for the Radon transform. We also obtain a generalization of the isomorphic version of the Shephard problem.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.13001/ela.2020.4941
