Let $n$ be a sufficiently large integer with $n\equiv 0\pmod 4$, and let $F_i \subseteq{[n]\choose 4}$, where $i\in [n/4]$. We show that if each vertex of $F_i$ is contained in more than ${n-1\choose 3}-{3n/4\choose 3}$ edges, then $\{F_1, \ldots ,F_{n/4}\}$ admits a rainbow matching, i.e., a set of $n/4$ edges consisting of one edge from each $F_i$. This generalizes a deep result of Khan J. Combin. Theory Ser. B, 116 (2016), pp. 333--366. on perfect matchings in 4-uniform hypergraphs.

Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulation with $n$ vertices, then $G$ contains at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. On the other hand, a recent result of Alahmadi, Aldred, and Thomassen states that there are exponentially many Hamiltonian cycles in 5-connected planar triangulations. In this paper, we consider 4-connected planar $n$-vertex triangulations $G$ that do not have too many separating 4-cycles or have minimum degree 5. We show that if $G$ has $O(n/{\log}_2 n)$ separating 4-cycles, then $G$ has $\Omega(n^2)$ Hamiltonian cycles, and if $\delta(G)\ge 5$, then $G$ has $2^{\Omega(n^{1/4})}$ Hamiltonian cycles. Both results improve previous work. Moreover, the proofs involve a “double wheel” structure, providing further evidence to the above conjecture.

We prove that, for any integers $k,l$ with $k\ge 3$ and $k/2 {n-l\choose k-l}-{(n-l)-m\choose k-l}$, then $H$ has a matching of size $m+1$. This improves upon an earlier result of Hàn, Person, and Schacht for the range $k/2

Tropical cyclone (TC) intensity estimation is an important task in meteorological research. Meanwhile, TC intensity estimation performance can be improved by developing advanced machine learning techniques using the newly emerged high-quality multispectral images (MSIs) acquired by FY-4 meteorological satellite of China. To this end, this article proposes a novel model, tensor-based convolutional neural network (TCNN). Not only being a deep network entirely formulated in tensor algebra, but TCNN also establishes the mathematical connections between tensor decomposition and CNN operations with tensor contraction. Moreover, TCNN adopts a multitask structure, which consists of a classification network for intensity categorization and a regression network for wind speed estimation. It allows the regression network to leverage the outcome of the classification network, thus ensuring intensity estimation accuracy. In addition, two alternative TCNN models, coupled TCNN (C-TCNN) and Tucker TCNN (T-TCNN), are designed to automatically deal with invalid band data in the FY-4 MSIs, which has been a practical issue with the data. Experimental results prove that the proposed network is accurate and functional. They also demonstrate the advantages of TCNN over other TC intensity estimation methods, showing that C-TCNN and T-TCNN outperform several classic models and the state-of-the-art models based on CNN.

Maximum wind speed (MWS) is an important characteristic of tropical cyclone (TC). Estimation of MWS with remote sensing images of TCs via machine learning is a relatively new and challenging task. Here we propose a novel and effective method, Regularized Tensor Network (RTN), to estimate MWS using multispectral images (MSIs). RTN is a transductive regression model, built on a deep Tensor Network (TN) combined with two regularizations: manifold learning and categorization error. Experimental results showed that RTN outperformed several classic regression methods as well as advanced models based on deep learning.

It is challenging to estimate wind speed of tropical cyclones directly using remote sensing image patterns. This paper approaches the task in two major steps: cyclone category estimation and wind speed regression. A novel framework based on Tensor Convolutional Neural Network (Tensor CNN) is proposed to solve the problem. Not only does the framework combine Tensor analysis for dimensionality reduction and deep neural networks for pattern recognition, the Tensor CNN also provides a unitary and concise mathematical representation form of the two significant models. The proposed framework is able to categorize cyclones by classification based on the Tensor CNN as well as exploit the estimated categories and predict the wind speed by a successive regression model. Experiments are conducted on multispectral imagery acquired by the FY-4 Satellite. Results show that the framework outperforms several classic models in cyclone category estimation and one state-of-the-art method, Deviation Angle Variance Technique (DAVT), in wind speed regression.

This paper investigates the resource allocation problem in device-to-device (D2D)-based vehicular communications, based on slow fading statistics of channel state information (CSI), to alleviate signaling overhead for reporting rapidly varying accurate CSI of mobile links. We consider the case when each vehicle-to-infrastructure (V2I) link shares spectrum with multiple vehicle-to-vehicle (V2V) links. Leveraging the slow fading statistical CSI of mobile links, we maximize the sum V2I capacity while guaranteeing the reliability of all V2V links. We propose a graph- based algorithm that uses graph partitioning tools to divide highly interfering V2V links into different clusters before formulating the spectrum sharing problem as a weighted 3-dimensional matching problem, which is then solved through adapting a high-performance approximation algorithm.

The minimum codegree threshold for a perfect matching in a $k$-graph with $n$ vertices was determined by Rödl, Ruciński, and Szemerédi for the case when $n\equiv 0\pmod k$. Recently, Han resolved the remaining cases when $n \not\equiv 0\pmod k$, establishing a conjecture of Rödl, Ruciński, and Szemerédi. In this paper, we determine the minimum codegree threshold for almost perfect matchings in $k$-partite $k$-graphs, answering a question of Rödl and Ruciński.

For any positive integer $m$, let $[m]:=\{1,\ldots,m\}$. Let $n,k,t$ be positive integers. Aharoni and Howard conjectured that if, for $i\in [t]$, $\mathcal{F}_i\subseteq [n]^k:= \{(a_1,\ldots,a_k): a_j\in [n] \mbox{ for } j\in [k]\}$ and $|\mathcal{F}_i|>(t-1)n^{k-1}$, then there exists $M\subseteq [n]^k$ such that $|M|=t$, $|M\cap \mathcal{F}_i|=1$ for $i\in [t]$ and $A\cap B=\emptyset$ for any $A,B\in M$. We show that this conjecture holds when $n\geq 3(k-1)(t-1)$. Let $n, t, k_1\ge k_2\geq \cdots\geq k_t $ be positive integers. Huang, Loh, and Sudakov asked for the maximum $\Pi_{i=1}^t |{\cal R}_i|$ over all ${\cal R}=\{{\cal R}_1, \ldots ,{\cal R}_t\}$ for which each ${\cal R}_i$ is a collection of $k_i$-subsets of $[n]$ and there does not exist a collection $M$ of subsets of $[n]$ such that $|M|=t$, $|M\cap \mathcal{R}_i|=1$ for $i\in [t]$ and $A\cap B=\emptyset$ for any $A,B\in M$. We show that for sufficiently large $n$, $\prod_{i=1}^t |\mathcal{R}_i|\leq {n-1 k_1-1}{n-1 k_2-1}\prod_{i=3}^{t}{n k_i}$ and that this bound is tight.

This paper investigates the resource allocation problem in device-to-device-based vehicular communications, based on slow fading statistics of channel state information (CSI), to alleviate signaling overhead for reporting rapidly varying accurate CSI of mobile links. We consider the case when each vehicle-to-infrastructure (V2I) link shares spectrum with multiple vehicle-to-vehicle (V2V) links. Leveraging the slow fading statistical CSI of mobile links, we maximize the sum V2I capacity while guaranteeing the reliability of all V2V links. We use graph partitioning tools to divide highly interfering V2V links into different clusters before formulating the spectrum sharing problem as a weighted 3-D matching problem. We propose a suite of algorithms, including a baseline graph-based resource allocation algorithm, a greedy resource allocation algorithm, and a randomized resource allocation algorithm, to address the performance-complexity tradeoffs. We further investigate resource allocation adaption in response to slow fading CSI of all vehicular links and develop a low-complexity randomized algorithm.

In this paper, we study path selection and power allocation problems for relay-aided systems with multiple source, relay, and destination nodes. To take fairness among different links into account, we aim at maximizing the minimum source-relay-destination link rate performance. We consider the scenario that the source node can be paired with any destination node. For this scenario, we decouple the original path selection and power allocation problem as two graph-based matching problems and develop algorithms to solve the formulated matching problems with and without sum power constraint, respectively. Numerical results show that our proposed algorithms outperform random matching algorithms in all scenarios and the corresponding performance gains increase with the number of nodes.

In this paper, we investigate robust resource allocation for cognitive radio networks. First, a resource allocation scheme based on stable matching is developed, which takes the preferences of both secondary users and primary users into account. To improve its robustness, we then discuss an ϵ-stable resource allocation scheme. With the help of the properties of ϵ-stable resource allocation, three edge-cutting algorithms are proposed. Numerical results show that the modified algorithms are robust to the channel state information variation.

A graph $G$ is said to satisfy the Vizing bound if $\chi(G)\le \omega(G)+1$, where $\chi(G)$ and $\omega(G)$ denote the chromatic number and clique number of $G$, respectively. The class of graphs satisfying the Vizing bound is clearly $\chi$-bounded in the sense of Gyárfás. It has been conjectured that if $G$ is triangle-free and fork-free, where the fork is obtained from $K_{1,4}$ by subdividing two edges, then $G$ satisfies the Vizing bound. We show that this is true if, in addition, $G$ is $C_5$-free.

In this paper, we investigate resource allocation for underlay cognitive radio (CR) networks, where the CR users coexist but do not cause unacceptable interference with licensed users. We focus on the energy efficiency (EE) performance of the system, where both throughput and energy consumption will be considered. We first formulate a sum-EE maximization problem and solve it by the Hungarian algorithm, called sum- EE-based scheme. Then, we take into account the preferences of CR users and licensed users and motivate a resource allocation scheme based on stable matching, called preference-based scheme. Numerical results demonstrate that the preference-based scheme has up to 50% performance gain on interference over the sum-EE-based scheme, while the former scheme has around 5% performance loss on EE performance compared to the latter one.

A classical theorem by Tutte ensures the existence of a Hamilton cycle in every finite 4-connected planar graph. Extensions of this result to infinite graphs require a suitable concept of an infinite cycle. Such a concept was provided by Diestel and Kühn, who defined circles to be homeomorphic images of the unit circle in the Freudenthal compactification of the (locally finite) graph. With this definition we prove a partial extension of Tutte's result to locally finite graphs.

Joint maximum-likelihood (JML) detector may be used in memoryless multiple-input multiple-output (MIMO) systems to obtain optimal detection performance. However, JML detector performs an exhaustive search and has prohibitively large decoding complexity. To reduce the complexity of MIMO signal detection, minimum mean-square-error (mmse) linear detector (LD), decision-feedback detector (DFD), group detector, and sphere detector (SD) may be used. In this correspondence, we propose a truncation based detector for low-complexity MIMO signal detection, and give theoretical insight into the design and performance of such a detector. We study bitruncation in detail and present two bitruncation approaches. These approaches have low-complexity, and computer simulation results show that they outperform mmse-LD and mmse-DFD

Jackson and Wormald conjecture that if G is a 3‐connected n‐vertex graph with maximum degree $d\ge 4$, then G has a cycle of length $\Omega(n^{\log_{d-1}2})$. We show that this conjecture holds when $d-1$ is replaced by $\max\{64,4d+1\}$. Our proof implies a cubic algorithm for finding such a cycle.

Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an $O(|V|^2)$ algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an $O(|V|^3)$ algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs.

In this paper, we describe an O(|V(G)||E(G)|) algorithm for finding a nonseparating planar chain in a 4-connected graph G, which will be used to decompose an arbitrary 4-connected graph into planar chains. This work was motivated by the study of a multitree approach to reliability in distributed networks, as well as the study of nonseparating induced paths in highly connected graphs.

In this paper we give a decomposition of a 4-connected graph G into nonseparating chains, which is similar to an ear decomposition of a 2-connected graph. We also give an $O(|V(G)|^2|E(G)|)$ algorithm that constructs such a decomposition. In applications, the asymptotic performance can often be improved to $O(|V(G)|^3)$.This decomposition will be used to find four independent spanning trees in a 4-connected graph.

The joint maximum-likelihood (JML) detector may be used in memoryless multiple input multiple output (MIMO) systems to obtain optimal detection performance. However the JML detector needs an exhaustive search and causes prohibitively large decoding complexity. To reduce the complexity of MIMO signal detection, the minimum mean-square-error (MMSE) linear detector (LD), decision-feedback detector (DFD) and sphere detector (SD) may be used. In this paper we develop bi-truncation based approaches for MIMO signal detection. The new approaches have low-complexity, and computer simulation results show that they outperform MMSE-LD and MMSE-DFD.

We study a fundamental tradeoff issue in designing a distributed hash table (DHT) in peer-to-peer (P2P) networks: the size of the routing table versus the network diameter. Observing that existing DHT schemes have either 1) a routing table size and network diameter both of O(log/sub 2/n), or 2) a routing table of size d and network diameter of O(n/sup 1/d/), S. Ratnasamy et al. (2001) asked whether this represents the best asymptotic "state-efficiency" tradeoffs. We show that some straightforward routing algorithms achieve better asymptotic tradeoffs. However, such algorithms all cause severe congestion on certain network nodes, which is undesirable in a P2P network. We rigorously define the notion of "congestion" and conjecture that the above tradeoffs are asymptotically optimal for a congestion-free network. The answer to this conjecture is negative in the strict sense. However, it becomes positive if the routing algorithm is required to eliminate congestion in a "natural" way by being uniform. We also prove that the tradeoffs are asymptotically optimal for uniform algorithms. Furthermore, for uniform algorithms, we find that the routing table size of O(log/sub 2/n) is a magic threshold point that separates two different "state-efficiency" regions. Our third result is to study the exact (instead of asymptotic) optimal tradeoffs for uniform algorithms. We propose a new routing algorithm that reduces the routing table size and the network diameter of Chord both by 21.4% without introducing any other protocol overhead, based on a novel number-theory technique. Our final result is to present Ulysses, a congestion-free nonuniform algorithm that achieves a better asymptotic "state-efficiency" tradeoff than existing schemes in the probabilistic sense, even under dynamic node joins/leaves.

Karger, Motwani, and Ramkumar Algorithmica, 18 (1997), pp. 82--98] have shown that there is no constant approximation algorithm to find a longest cycle in a Hamiltonian graph, and they conjectured that this is the case even for graphs with bounded degree. On the other hand, Feder, Motwani, and Subi [SIAM J. Comput., 31 (2002), pp. 1596--1607] have shown that there is a polynomial time algorithm for finding a cycle of length $n^{\log_32}$ in a 3-connected cubic n-vertex graph. In this paper, we show that if G is a 3-connected n-vertex graph with maximum degree at most d, then one can find, in O(n 3 ) time, a cycle in G of length at least $\Omega(n^{\log_b2})$, where $b=2(d-1)^2+1$.

A number of distributed hash table (DHT)-based protocols have been proposed to address the issue of scalability in peer-to-peer networks. In this paper, we present Ulysses, a peer-to-peer network based on the butterfly topology that achieves the theoretical lower bound of (log n)/(log log n)on network diameter when the average routing table size at nodes is no more than log n. Compared to existing DHT-based schemes with similar routing table size, Ulysses reduces the network diameter by a factor of log log n. which is 2-4 for typical configurations. This translates into the same amount of reduction on query latency and average traffic per link/node. In addition, Ulysses maintains the same level of robustness in terms of routing in the face of faults and recovering from graceful/ungraceful joins and departures, as provided by existing DHT-based schemes. The performance of the protocol has been evaluated using both analysis and simulation.

We prove that given any fixed edge ra in a 4-connected graph G, there exists a cycle C through ra such that G-(V(C)-{r}) is 2-connected. This will provide the first step in a decomposition for 4-connected graphs. We also prove that, for any given edge e in a 5-connected graph G, there exists an induced cycle C through e in G such that G-V(C) is 2-connected. This provides evidence for a conjecture of Lovász.