The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)

The vertices of Kneser graph $K(n,k)$ are the subsets of $\{1,2,\dots ,n\}$ of cardinality $k$, two vertices are adjacent if and only if they are disjoint. The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ with two vertices adjacent if their distance in $G$ is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when $n=2k+1$. It is believed that $\chi \left(K^2(2k+1,k)\right)=2k+c$ where $c$ is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: $8k∕3+20∕3$ for 1$k\ge 3$ (Kim and Park, 2014) and $32k∕15+32$ for $k\ge 7$ (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to $\chi \left(K^2(2k+1,k)\right)\le 5k∕2+c$, where $c$ is a constant in $\{5∕2,9∕2,5,6\}$, depending on $k\ge 2$.     

Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are (3,1)-colorable

Given a nonnegative integer $d$ and a positive integer $k$, a graph $G$ is said to be $(k,d)$-colorable if the vertices of $G$ can be colored with $k$ colors such that every vertex has at most $d$ neighbors receiving the same color as itself. Let $?$ be the family of planar graphs without $3$-cycles adjacent to cycles of length 3 or 5. This paper proves that everyone in $?$ is $(3,1)$-colorable. This is the best possible in the sense that there are members in $?$ which are not $(3,0)$-colorable.     

Fermat-type configurations of lines in P3 and the containment problem

The purpose of this note is to show a new series of examples of homogeneous ideals I in $\mathbb{K}[x,y,z,w]$ for which the containment $I^{(3)}?I^2$ fails. These ideals are supported on certain arrangements of lines in ${\mathbb{P}}^3$, which resemble Fermat configurations of points in ${\mathbb{P}}^2$, see [14]. All examples exhibiting the failure of the containment $I^{(3)}?I^2$ constructed so far have been supported on points or cones over configurations of points. Apart from providing new counterexamples, these ideals seem quite interesting on their own.     

On the spanning connectivity of the generalized Petersen graphs P(n,3)

In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph $P(n,3)$. We showed that the $P(n,3)$ is 3-spanning connected for odd $n$. Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the $P(n,3)$. In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for $P(n?6,3)$, where a lattice tail is a trail in the lattice model that represents a path in $P(n,3)$.     

A degree condition for a graph to have (a,b)-parity factors

Let $a$ and $b$ be two positive integers such that $a\le b$ and $a\equiv b(mod2)$. A graph $F$ is an $(a,b)$-parity factor of a graph $G$ if $F$ is a spanning subgraph of $G$ and for all vertices $v\in V\left(F\right)$, $d_F\left(v\right)\equiv b(mod2)$ and $a\le d_F\left(v\right)\le b$. In this paper we prove that every connected graph $G$ with $n\ge b(a+b)(a+b+2)∕\left(2a\right)$ vertices has an $(a,b)$-parity factor if $na$ is even, $\delta \left(G\right)\ge (b?a)∕a+a$, and for any two nonadjacent vertices $u,v\in V\left(G\right)$, $max\{d_G\left(u\right),d_G\left(v\right)\}\ge \frac{an}{a+b}$. This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998).     

Moments about the mean of the size of a self-conjugate (s,t)-core partition

Johnson proved that if $s,t$ are coprime integers, then the $r$th moment of the size of an $(s,t)$-core is a polynomial of degree $2r$ in $t$ for fixed $s$. After that, by defining a statistic size on elements of affine Weyl group, which is preserved under the bijection between minimal coset representatives of ${\stackrel{?}{\mathfrak{S}}}_t∕{\mathfrak{S}}_t$ and $t$-cores, Thiel and Williams obtained the variance and the third moment about the mean of the size of an $(s,t)$-core. Later, Ekhad and Zeilberger stated the first six moments about the mean of the size of an $(s,t)$-core and the first nine moments about the mean of the size of an $(s,s+1)$-core using Maple. To get the moments about the mean of the size of a self-conjugate $(s,t)$-core, we proceed to follow the approach of Thiel and Williams, however, their approach does not seem to directly apply to the self-conjugate case. In this paper, following Johnson’s approach, by Ehrhart theory and Euler–Maclaurin theory, we prove that if $s,t$ are coprime integers, then the $r$th moment about the mean of the size of a self-conjugate $(s,t)$-core is a quasipolynomial of period 2 and degree $2r$ in $t$ for fixed odd $s$. Then, based on a bijection of Ford, Mai and Sze between self-conjugate $(s,t)$-cores and lattice paths in $?\frac{s}{2}?\times ?\frac{t}{2}?$ rectangle and a formula of Chen, Huang and Wang on the size of self-conjugate $(s,t)$-cores, we obtain the variance, the third moment and the fourth moment about the mean of the size of a self-conjugate $(s,t)$-core.     

Subspace partitions of Fqn containing direct sums

Let $q$ be a prime power and $n$ be a positive integer. A subspace partition of $V={\mathbb{F}}_q^n$, the vector space of dimension $n$ over ${\mathbb{F}}_q$, is a collection $\Pi$ of subspaces of $V$ such that each nonzero vector of $V$ is contained in exactly one subspace in $\Pi$; the multiset of dimensions of subspaces in $\Pi$ is then called a Gaussian partition of $V$. We say that $\Pi$contains a direct sum if there exist subspaces $W_1,\dots ,W_k\in \Pi$ such that $W_1\oplus ?\oplus W_k=V$. In this paper, we study the problem of classifying the subspace partitions that contain a direct sum. In particular, given integers $a_1$ and $a_2$ with $n>a_1>a_2\ge 1$, our main theorem shows that if $\Pi$ is a subspace partition of ${\mathbb{F}}_q^n$ with $m_i$ subspaces of dimension $a_i$ for $i=1,2$, then $\Pi$ contains a direct sum when $a_1{x}_1+a_2{x}_2=n$ has a solution $(x_1,x_2)$ for some integers $x_1,x_2\ge 0$ and $m_2$ belongs to the union $I$ of two natural intervals. The lower bound of $I$ captures all subspace partitions with dimensions in $\{a_1,a_2\}$ that are currently known to exist. Moreover, we show the existence of infinite classes of subspace partitions without a direct sum when $m_2?I$ or when the condition on the existence of a nonnegative integral solution $(x_1,x_2)$ is not satisfied. We further conjecture that this theorem can be extended to any number of distinct dimensions, where the number of subspaces in each dimension has appropriate bounds. These results offer further evidence of the natural combinatorial relationship between Gaussian and integer partitions (when $q\to 1$) as well as subspace and set partitions.     

A sharp bound on the expected number of upcrossings of an L2-bounded Martingale

For a martingale $M$ starting at $x$ with final variance ${\sigma }^2$, and an interval $(a,b)$, let $\Delta =\frac{b?a}{\sigma }$ be the normalized length of the interval and let $\delta =\frac{|x?a|}{\sigma }$ be the normalized distance from the initial point to the lower endpoint of the interval. The expected number of upcrossings of $(a,b)$ by $M$ is at most $\frac{\sqrt{1+{\delta }^2}?\delta }{2\Delta }$ if ${\Delta }^2\le 1+{\delta }^2$ and at most $\frac{1}{1+{(\Delta +\delta )}^2}$ otherwise. Both bounds are sharp, attained by Standard Brownian Motion stopped at appropriate stopping times. Both bounds also attain the Doob upper bound on the expected number of upcrossings of $(a,b)$ for submartingales with the corresponding final distribution. Each of these two bounds is at most $\frac{\sigma }{2(b?a)}$, with equality in the first bound for $\delta =0$. The upper bound $\frac{\sigma }{2}$ on the length covered by $M$ during upcrossings of an interval restricts the possible variability of a martingale in terms of its final variance. This is in the same spirit as the Dubins & Schwarz sharp upper bound $\sigma$ on the expected maximum of $M$ above $x$, the Dubins & Schwarz sharp upper bound $\sigma \sqrt{2}$ on the expected maximal distance of $M$ from $x$, and the Dubins, Gilat & Meilijson sharp upper bound $\sigma \sqrt{3}$ on the expected diameter of $M$.     

On q-Steiner systems from rank metric codes

In this paper we prove that rank metric codes with special properties imply the existence of $q$-analogs of suitable designs. More precisely, we show that the minimum weight vectors of a $[2d,d,d]$ dually almost MRD code $C\le {\mathbb{F}}_{q^m}^{2d}$$(2d\le m)$ which has no code words of rank weight $d+1$ form a $q$-Steiner system $S{(d?1,d,2d)}_q$. This is the q-analog of a result in classical coding theory and it may be seen as a first step to prove a q-analog of the famous Assmus–Mattson Theorem.     

List r-hued chromatic number of graphs with bounded maximum average degrees

For integers $k,r>0$, a $(k,r)$-coloring of a graph $G$ is a proper coloring $c$ with at most $k$ colors such that for any vertex $v$ with degree $d\left(v\right)$, there are at least min$\{d\left(v\right),r\}$ different colors present at the neighborhood of $v$. The $r$-hued chromatic number of $G$, ${\chi }_r\left(G\right)$, is the least integer $k$ such that a $(k,r)$-coloring of $G$ exists. The list$r$-hued chromatic number${\chi }_{L,r}\left(G\right)$ of $G$ is similarly defined. Thus if $\Delta \left(G\right)\ge r$, then ${\chi }_{L,r}\left(G\right)\ge {\chi }_r\left(G\right)\ge r+1$. We present examples to show that, for any sufficiently large integer $r$, there exist graphs with maximum average degree less than 3 that cannot be $(r+1,r)$-colored. We prove that, for any fraction $q<\frac{14}{5}$, there exists an integer $R=R\left(q\right)$ such that for each $r\ge R$, every graph $G$ with maximum average degree $q$ is list $(r+1,r)$-colorable. We present examples to show that for some $r$ there exist graphs with maximum average degree less than 4 that cannot be $r$-hued colored with less than $\frac{3r}{2}$ colors. We prove that, for any sufficiently small real number $?>0$, there exists an integer $h=h\left(?\right)$ such that every graph $G$ with maximum average degree $4??$ satisfies ${\chi }_{L,r}\left(G\right)\le r+h\left(?\right)$. These results extend former results in Bonamy et al. (2014).     

On 3-stable number conditions in n-connected claw-free graphs

For a subgraph $X$ of $G$, let ${\alpha }_G^3\left(X\right)$ be the maximum number of vertices of $X$ that are pairwise distance at least three in $G$. In this paper, we prove three theorems. Let $n$ be a positive integer, and let $H$ be a subgraph of an $n$-connected claw-free graph $G$. We prove that if $n\ge 2$, then either $H$ can be covered by a cycle in $G$, or there exists a cycle $C$ in $G$ such that ${\alpha }_G^3(H?V\left(C\right))\le {\alpha }_G^3\left(H\right)?n$. This result generalizes the result of Broersma and Lu that $G$ has a cycle covering all the vertices of $H$ if ${\alpha }_G^3\left(H\right)\le n$. We also prove that if $n\ge 1$, then either $H$ can be covered by a path in $G$, or there exists a path $P$ in $G$ such that ${\alpha }_G^3(H?V\left(P\right))\le {\alpha }_G^3\left(H\right)?n?1$. By using the second result, we prove the third result. For a tree $T$, a vertex of $T$ with degree one is called a leaf of $T$. For an integer $k\ge 2$, a tree which has at most $k$ leaves is called a $k$-ended tree. We prove that if ${\alpha }_G^3\left(H\right)\le n+k?1$, then $G$ has a $k$-ended tree covering all the vertices of $H$. This result gives a positive answer to the conjecture proposed by Kano et al. (2012).     

Homomorphism complexes and k-cores

For any fixed graph $G$, we prove that the topological connectivity of the graph homomorphism complex Hom($G,K_m$) is at least $m?D\left(G\right)?2$, where $D\left(G\right)={max}_{H?G}\delta \left(H\right)$, for $\delta \left(H\right)$ the minimum degree of a vertex in a subgraph $H$. This generalizes a theorem of C?uki? and Kozlov, in which the maximum degree $\Delta \left(G\right)$ was used in place of $D\left(G\right)$, and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, $\chi \left(G\right)\le D\left(G\right)+1$, as $\chi \left(G\right)=min\{m:\text{Hom}(G,K_m)\ne ?\}$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom$(G(n,p),K_m)$ when $p=c∕n$ for a fixed constant $c>0$.