Monochromatic subgraphs in randomly colored graphons

Let $T(H,G_n)$ be the number of monochromatic copies of a fixed connected graph $H$ in a uniformly random coloring of the vertices of the graph $G_n$. In this paper we give a complete characterization of the limiting distribution of $T(H,G_n)$, when ${\left\{G_n\right\}}_{n\ge 1}$ is a converging sequence of dense graphs. When the number of colors grows to infinity, depending on whether the expected value remains bounded, $T(H,G_n)$ either converges to a finite linear combination of independent Poisson variables or a normal distribution. On the other hand, when the number of colors is fixed, $T(H,G_n)$ converges to a (possibly infinite) linear combination of independent centered chi-squared random variables. This generalizes the classical birthday problem, which involves understanding the asymptotics of $T(K_s,K_n)$, the number of monochromatic $s$-cliques in a complete graph $K_n$ ($s$-matching birthdays among a group of $n$ friends), to general monochromatic subgraphs in a network.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

Degree powers in graphs with a forbidden forest

Given a positive integer $p$ and a graph $G$ with degree sequence $d_1,\dots ,d_n$, we define $e_p\left(G\right)={\sum }_{i=1}^n{d}_i^p$. Caro and Yuster introduced a Turán-type problem for $e_p\left(G\right)$: Given a positive integer $p$ and a graph $H$, determine the function ${\text{ex}}_p(n,H)$, which is the maximum value of $e_p\left(G\right)$ taken over all graphs $G$ on $n$ vertices that do not contain $H$ as a subgraph. Clearly, ${\text{ex}}_1(n,H)=2\text{ex}(n,H)$, where $\text{ex}(n,H)$ denotes the classical Turán number. Caro and Yuster determined the function ${\text{ex}}_p(n,P_{?})$ for sufficiently large $n$, where $p\ge 2$ and $P_{?}$ denotes the path on $?$ vertices. In this paper, we generalise this result and determine ${\text{ex}}_p(n,F)$ for sufficiently large $n$, where $p\ge 2$ and $F$ is a linear forest. We also determine ${\text{ex}}_p(n,S)$, where $S$ is a star forest; and ${\text{ex}}_p(n,B)$, where $B$ is a broom graph with diameter at most six.     

A note on the weak (2,2)-Conjecture

Let $G=(V,E)$ be any graph without isolated edges. The well known 1–2–3 Conjecture asserts that the edges of $G$ can be weighted with $1,2,3$ so that adjacent vertices have distinct weighted degrees, i.e. the sums of their incident weights. It was independently conjectured that if $G$ additionally has no isolated triangles, then it can be edge decomposed into two subgraphs $G_1,G_2$ which fulfil the 1–2–3 Conjecture with just weights 1,2, i.e. such that there exist weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ so that for every $uv\in E$, if $uv\in E\left(G_i\right)$ then $d_{{\omega }_i}\left(u\right)\ne d_{{\omega }_i}\left(v\right)$, where $d_{{\omega }_i}\left(v\right)$ denotes the sum of weights incident with $v\in V$ in $G_i$ for $i=1,2$. We apply the probabilistic method to prove that the known weakening of this so-called Standard (2,2)-Conjecture holds for graphs with minimum degree large enough. Namely, we prove that if $\delta \left(G\right)\ge 3660$, then $G$ can be decomposed into graphs $G_1,G_2$ for which weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ exist so that for every $uv\in E$, $d_{{\omega }_1}\left(u\right)\ne d_{{\omega }_1}\left(v\right)$ or $d_{{\omega }_2}\left(u\right)\ne d_{{\omega }_2}\left(v\right)$. In fact we prove a stronger result, as one of the weightings is redundant, i.e. uses just weight 1.     

On invariant fields of vectors and covectors

Let ${\mathbb{F}}_q$ be the finite field of order q. Let G be one of the three groups $\mathrm{GL}(n,{\mathbb{F}}_q)$, $\mathrm{SL}(n,{\mathbb{F}}_q)$ or $\mathrm{U}(n,{\mathbb{F}}_q)$ and let W be the standard n-dimensional representation of G. For non-negative integers m and d we let $mW\oplus d{W}^{?}$ denote the representation of G given by the direct sum of m vectors and d covectors. We exhibit a minimal set of homogeneous invariant polynomials $\{{?}_1,{?}_2,\dots ,{?}_{(m+d)n}\}?{\mathbb{F}}_q{[mW\oplus d{W}^{?}]}^G$ such that ${\mathbb{F}}_q{(mW\oplus d{W}^{?})}^G={\mathbb{F}}_q({?}_1,{?}_2,\dots ,{?}_{(m+d)n})$ for all cases except when $md=0$ and $G=\mathrm{GL}(n,{\mathbb{F}}_q)$ or $\mathrm{SL}(n,{\mathbb{F}}_q)$.     

Connected k-dominating graphs

For a graph $G=(V,E)$, the $k$-dominating graph $D_k\left(G\right)$ of $G$ has vertices corresponding to the dominating sets of $G$ having cardinality at most $k$, where two vertices of $D_k\left(G\right)$ are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of $G$ by $\gamma \left(G\right)$ and $\Gamma \left(G\right)$, respectively, and the smallest integer $\epsilon$ for which $D_k\left(G\right)$ is connected for all $k\ge \epsilon$ by $d_0\left(G\right)$. It is known that $\Gamma \left(G\right)+1\le d_0\left(G\right)\le \left|V\right|$, but constructing a graph $G$ such that $d_0\left(G\right)>\Gamma \left(G\right)+1$ appears to be difficult.We present two related constructions. The first construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $G_{k,r}$ such that $\Gamma \left(G_{k,r}\right)=k$, $\gamma \left(G_{k,r}\right)=r+1$ and $d_0\left(G_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)?1$. The second construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $Q_{k,r}$ such that $\Gamma \left(Q_{k,r}\right)=k$, $\gamma \left(Q_{k,r}\right)=r$ and $d_0\left(Q_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)$.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

On the number of harmonic frames

There is a finite number $h_{n,d}$ of tight frames of n distinct vectors for ${\mathbb{C}}^d$ which are the orbit of a vector under a unitary action of the cyclic group ${\mathbb{Z}}_n$. These cyclic harmonic frames (or geometrically uniform tight frames) are used in signal analysis and quantum information theory, and provide many tight frames of particular interest. Here we investigate the conjecture that $h_{n,d}$ grows like $n^{d-1}$. By using a result of Laurent which describes the set of solutions of algebraic equations in roots of unity, we prove the asymptotic estimate$h_{n,d}\approx \frac{n^d}{\phi (n)}\ge n^{d-1},n\to \infty .$ By using a group theoretic approach, we also give some exact formulas for $h_{n,d}$, and estimate the number of cyclic harmonic frames up to projective unitary equivalence.     

Twisted Steinberg algebras

We introduce twisted Steinberg algebras over a commutative unital ring R. These generalise Steinberg algebras and are a purely algebraic analogue of Renault's twisted groupoid C*-algebras. In particular, for each ample Hausdorff groupoid G and each locally constant 2-cocycle σ on G taking values in the units $R^{\times }$, we study the algebra $A_R(G,\sigma )$ consisting of locally constant compactly supported R-valued functions on G, with convolution and involution “twisted” by σ. We also introduce a “discretised” analogue of a twist Σ over a Hausdorff étale groupoid G, and we show that there is a one-to-one correspondence between locally constant 2-cocycles on G and discrete twists over G admitting a continuous global section. Given a discrete twist Σ arising from a locally constant 2-cocycle σ on an ample Hausdorff groupoid G, we construct an associated twisted Steinberg algebra $A_R(G;\mathrm{\Sigma })$, and we show that it coincides with $A_R(G,{\sigma }^{?1})$. Given any discrete field ${\mathbb{F}}_d$, we prove a graded uniqueness theorem for $A_{{\mathbb{F}}_d}(G,\sigma )$, and under the additional hypothesis that G is effective, we prove a Cuntz–Krieger uniqueness theorem and show that simplicity of $A_{{\mathbb{F}}_d}(G,\sigma )$ is equivalent to minimality of G.     

A note on the Hambleton-Taylor-Williams conjecture

I. Hambleton, L. Taylor and B. Williams conjectured a general formula in the spirit of H. Lenstra for the decomposition of $G_n(RG)$ for any finite group G and noetherian ring R. The conjectured decomposition was shown to hold for some large classes of finite groups. D. Webb and D. Yao discovered that the conjecture failed for the symmetric group $S_5$, but remarked that it still might be reasonable to expect the HTW-decomposition for solvable groups. In this paper we show that the solvable group $\mathrm{SL}(2,{\mathbb{F}}_3)$ is also a counterexample to the conjectured HTW-decomposition. Nevertheless, we prove that for any finite group G the rank of $G_1(\mathbb{Z}G)$ does not exceed the rank of the expression in the HTW-decomposition. We also show that the HTW-decomposition predicts correct torsion for $G_1(\mathbb{Z}G)$ for any finite group G. Furthermore, we prove that for any degree other than $n=1$ the conjecture gives a correct prediction for the rank of $G_n(\mathbb{Z}G)$.     

Daisy cubes and distance cube polynomial

Let $X\subseteq {\{0,1\}}^n$. The daisy cube $Q_n\left(X\right)$ is introduced as the subgraph of $Q_n$ induced by the union of the intervals $I(x,0^n)$ over all $x\in X$. Daisy cubes are partial cubes that include Fibonacci cubes, Lucas cubes, and bipartite wheels. If $u$ is a vertex of a graph $G$, then the distance cube polynomial $D_{G,u}(x,y)$ is introduced as the bivariate polynomial that counts the number of induced subgraphs isomorphic to $Q_k$ at a given distance from the vertex $u$. It is proved that if $G$ is a daisy cube, then $D_{G,0^n}(x,y)=C_G(x+y-1)$, where $C_G\left(x\right)$ is the previously investigated cube polynomial of $G$. It is also proved that if $G$ is a daisy cube, then $D_{G,u}(x,-x)=1$ holds for every vertex $u$ in $G$.