d-matching in 3-uniform hypergraphs

A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. A $d$-matching in a 3-uniform hypergraph $H$ is a matching of size $d$. Let $V_1,V_2$ be a partition of $n$ vertices such that $\left|V_1\right|=2d?1$ and $\left|V_2\right|=n?2d+1$. Denote by $E_3(2d?1,n?2d+1)$ the 3-uniform hypergraph with vertex set $V_1\cup V_2$ consisting of all those edges which contain at least two vertices of $V_1$. Let $H$ be a 3-uniform hypergraph of order $n\ge 9d^2$ such that $deg\left(u\right)+deg\left(v\right)>2\left[\left(\genfrac{}{}{0ex}{}{n?1}{2}\right)?\left(\genfrac{}{}{0ex}{}{n?d}{2}\right)\right]$ for any two adjacent vertices $u,v\in V\left(H\right)$. In this paper, we prove $H$ contains a $d$-matching if and only if $H$ is not a subgraph of $E_3(2d?1,n?2d+1)$.     

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

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.     

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.     

2p-cycle decompositions of some regular graphs and digraphs

In this paper, we consider $2k$-cycle decomposition of $K_m\times K_n$ and directed $2k$-cycle decompositions of ${(K_m°{\overline{K}}_n)}^1$ and ${(K_m\times K_n)}^1$, where $°$ and $\times$ denote the wreath product and tensor product of graphs, respectively. Using the results obtained here, we prove that for $m,n\ge 3$, the obvious necessary conditions for the existence of a $C_{2k}$-decomposition of $K_m\times K_n$ are sufficient whenever $k\in \{p,2^{?}\},$ where $p$ is a prime and $?\ge 2$. Also, we show that the necessary conditions for the existence of ${\overrightarrow{C}}_{2p}$-decompositions of ${(K_m°{\overline{K}}_n)}^1$ and ${(K_m\times K_n)}^1$ are sufficient whenever $p$ is a prime, where ${\overrightarrow{C}}_{2p}$ denotes the directed cycle of length $2p$.     

Characterization of the induced matching extendable graphs with 2n vertices and 3n edges

A graph $G$ is induced matching extendable or IM-extendable if every induced matching of $G$ is contained in a perfect matching of $G$. In 1998, Yuan proved that a connected IM-extendable graph on $2n$ vertices has at least $3n?2$ edges, and that the only IM-extendable graph with $2n$ vertices and $3n?2$ edges is $T\times K_2$ , where $T$ is an arbitrary tree on $n$ vertices. In 2005, Zhou and Yuan proved that the only IM-extendable graph with $2n\ge 6$ vertices and $3n?1$ edges is $T\times K_2+e$, where $T$ is an arbitrary tree on $n$ vertices and $e$ is an edge connecting two vertices that lie in different copies of $T$ and have distance 3 between them in $T\times K_2$. In this paper, we introduced the definition of $Q$-joint graph and characterized the connected IM-extendable graphs with $2n\ge 4$ vertices and $3n$ edges.     

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

Properties of minimally t-tough graphs

A graph $G$ is minimally $t$-tough if the toughness of $G$ is $t$ and the deletion of any edge from $G$ decreases the toughness. Kriesell conjectured that for every minimally $1$-tough graph the minimum degree $\delta \left(G\right)=2$. We show that in every minimally $1$-tough graph $\delta \left(G\right)\le \frac{n}{3}+1$. We also prove that every minimally $1$-tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number $t$ any graph can be embedded as an induced subgraph into a minimally $t$-tough graph.     

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

A regularity theory for quasi-linear Stochastic PDEs in weighted Sobolev spaces

We study the second-order quasi-linear stochastic partial differential equations (SPDEs) defined on $C^1$-domains. The coefficients are random functions depending on $t,x$ and the unknown solutions. We prove the uniqueness and existence of solutions in appropriate Sobolev spaces, and in addition, we obtain $L_p$ and Hölder estimates of both the solution and its gradient.     

A pairwise almost disjoint subspace of kN of maximal dimension

We show that if k is an infinite field, then there exists a subspace $W?k^{\mathbb{N}}$ of dimension $|k{|}^{{\mathrm{?}}_0}$, such that no nonzero member of W has infinitely many zeros. This generalizes a result from a paper by Bergman and Nahlus, and partly answers another question from the same paper.     

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

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