Search

For a graph G and a set Z of four distinct vertices of G, a diamond on Z is a subgraph of G such that, for some labeling Z = { v 1 , v 2 , v 3 , v 4 } , there are three internally disjoint paths P 1 , P 2 , P 3 with end vertices v 1 , v 2 with v 3 , v 4 on P 1 , P 2 , respectively. Therefore, this yields a K 4 − -subdivision with branch vertices on Z. We characterize graphs G that contain no diamond on a prescribed set Z of four vertices, under the assumption that for every v ∈ Z there are three paths of G from v to Z − { v } , mutually disjoint except for v. Moreover, we can find two “different” such subdivisions, if one exists. Our proof is based on Mader's S-paths theorem.

Community detection is an important area of research in social media mining. Numerous algorithms have been developed to detect disjoint, overlapping, and dynamic communities in a network. However, most of the existing algorithms do not consider the influence of each node in a group, which may be different and can affect the result of community detection. In this paper, we have proposed a novel Louvain-based algorithm named “NI-Louvain,” which considers the influence of each node in a group that not only detects community but also most influential nodes in the community. The proposed algorithm works in three steps. First, the input graph is processed to reduce its density. This is done by calculating cliques from the graph. In second step, Louvain's multilevel algorithm is applied to this clique graph. The resultant community obtained has a better modularity value than the communities obtained from existing algorithms like edge betweenness, label propagation, leading eigen, Louvain, fast greedy, walktrap, and infomap. In the third step, the nodes of resultant communities are transformed back to the nodes of the original graph. This step is beneficial in detecting overlapping communities, fuzzy membership of each node, most influential node in each community formed, and outlier nodes.

An asymmetric coloring of a graph is a coloring of its vertices that is not preserved by any non-identity automorphism of the graph. The motion of a graph is the minimal degree of its automorphism group, i.e., the minimum number of elements displaced by any non-identity automorphism. In this paper we confirm Tom Tucker's "Infinite Motion Conjecture" that connected locally finite graphs with infinite motion admit an asymmetric 2-coloring. We infer this from the more general result that the inverse limit of a sequence of finite permutation groups with disjoint domains, viewed as a permutation group on the union of those domains, admits an asymmetric 2-coloring. The proof is based on the study of the interaction between epimorphisms of finite permutation groups and the structure of the setwise stabilizers of subsets of their domains., Comment: V.2 updates: Choi 1972 ref. added, Sec. 8.3 (Mathieu groups) updated, question about $M_{24}$ deleted from "Open questions." New material: New Sec. 14 added, incl. two conjectures. Minor changes made for improved clarity throughout the paper. None of the updates affects the main results or their proofs

We introduce an object called a tree growing sequence (TGS) in an effort to generalize bijective correspondences between G -parking functions, spanning trees, and the set of monomials in the Tutte polynomial of a graph G . A tree growing sequence determines an algorithm which can be applied to a single function, or to the set P G , q of G -parking functions. When the latter is chosen, the algorithm uses splitting operations – inspired by the recursive definition of the Tutte polynomial – to iteratively break P G , q into disjoint subsets. This results in bijective maps τ and ρ from P G , q to the spanning trees of G and Tutte monomials, respectively. We compare the TGS algorithm to Dhar’s algorithm and the family described by Chebikin and Pylyavskyy in 2005. Finally, we compute a Tutte polynomial of a zonotopal tiling using analogous splitting operations.

In an observational study, one is given disjoint samples of treatment units and control (untreated) units, and the goal is to compare outcomes between the two samples in order to estimate a treatment effect. A complication is that the treatment and control units often differ on important pre-treatment attributes, and these differences, referred to as covariate imbalance, can bias the estimate. One method to correct for covariate imbalance is to select a subset of the control sample that has minimum imbalance with respect to the treatment sample, and then use this control subset for estimating the treatment effect. While this optimization problem is NP-hard in general, certain special cases can be solved efficiently. Specifically, the variant of this optimization problem with one covariate is easy to solve, the variant with three or more covariates is NP-hard, and the variant with two covariates is solvable in polynomial time. We present several network flow formulations for the problem of minimizing imbalance on two nominal covariates. First, we present a minimum cost network flow formulation for solving the problem with the constraint that the control subset must have the same size as the treatment sample. We then derive an improved maximum flow formulation. For alternate size restrictions on the control subset, we use a proportional imbalance objective which leads to non-integral supplies and demands in the preceding network flow formulations. We then derive an alternate minimum cost network flow formulation that ensures integrality and solves the proportional imbalance problem in polynomial time.

After a disaster, often roads are damaged and blocked, hindering accessibility for relief efforts. It is essential to dispatch work teams to restore the blocked roads by clearance or repair operations. With the goal of enabling access between critical locations in the disaster area in shortest time, we propose algorithms that determine the schedule and routes of multiple work teams. We minimize the total latency of reaching the critical locations, where the latency of a location is defined as the time it takes from the start of the operation until its first visit by one of the work teams. Coordination among the teams is needed since some blocked edges might be opened by a certain team and utilized by other teams later on. First, we develop an exact mathematical model that handles the coordination requirement. After observing the intractability of this formulation, we introduce two heuristic methods and a lower bounding procedure. In the first method, we develop a mathematical model based on a novel multi-level network representation that yields solutions with disjoint paths. Given that it does not coordinate the teams, we present a matheuristic based on a cluster-first-route-second approach embedded into a local search algorithm together with an additional coordination step to obtain alternative solutions with higher quality and in a shorter time. We test our heuristics on data sets coming from a real network from the literature (180 instances) and randomly generated ones (640 instances) and observe the superiority of the solutions obtained by incorporation of coordination., NA

There are numerous coverage algorithms which efficiently monitor targets in sensor networks by dividing the sensor network into cover sets where each cover monitors all the targets. Creating maximum number of cover sets is a NP Complete problem and therefore problems providing subprime solutions have been proposed. In this paper we propose a novel and energy efficient target coverage algorithm that produces disjoint as well as non-disjoint cover sets. Our proposed solution along with generating cover sets for monitoring targets also gives the energy optimized minimum path from sink to the sensor node and from cover set to the sink. Our algorithm keeps a track of the number of targets a sensor is monitoring along with the energy remaining to find a path which is energy optimized to increase the lifetime of the sensor network. Through simulations, we have shown that our proposed algorithm outperforms similar algorithms found in literature. The increased network lifetime provided by energy optimized path and energy efficient cover sets makes our algorithm desirable for a wider range of applications.

We characterise directed graphs consisting of disjoint cycles via their talented monoids. We show that a graph $E$ consists of disjoint cycles precisely when its talented monoid $T_E$ has a certain Jordan-H\"older composition series. These are graphs whose associated Leavitt path algebras have finite Gelfand-Kirillov dimension (GKdim). We show that this dimension can be determined as the length of certain ideal series of the talented monoid. Since $T_E$ is the positive cone of the graded Grothendieck group $K_0^{gr}(L_K (E))$, we conclude that for graphs $E$ and $F$, if $K_0^{gr}(L_K (E))\cong K_0^{gr}(L_K (F))$ then $GKdim L_K(E) = GKdim L_K(F)$, thus providing more evidence for the Graded Classification Conjecture for Leavitt path algebras., Comment: 13 pages. Comments welcome!

Occupancy grids encode for hot spots on a map that is represented by a two dimensional grid of disjoint cells. The problem is to recursively update the probability that each cell in the grid is occupied, based on a sequence of sensor measurements from a moving platform. In this paper, we provide a new Bayesian framework for generating these probabilities that does not assume statistical independence between the occupancy state of grid cells. This approach is made analytically tractable through the use of binary asymmetric channel models that capture the errors associated with observing the occupancy state of a grid cell. Binary-valued measurement vectors are the thresholded output of a sensor in a radar, sonar, or other sensory system. We compare the performance of the proposed framework to that of the classical formulation for occupancy grids. The results show that the proposed framework identifies occupancy grids with lower false alarm and miss detection rates, and requires fewer observations of the surrounding area, to generate an accurate estimate of occupancy probabilities when compared to conventional formulations.

To aggregate useful information among diversified sources, a hotspot research topic called truth discovery has emerged in recent years. Existing truth discovery methods attempt to infer the true attribute values for the entities by identifying and trusting reliable data sources. However, all these methods neglect the relations among different entities, which play important roles in truth discovery task. When reliable data sources cannot provide sufficient information of entities, the true attribute values of these entities can still be inferred by propagating trustworthy information from related entities. Motivated by this, in this paper, we introduce the constrained truth discovery problem. We incorporate denial constraints, a universally quantified first-order logic formalism, into the process of truth discovery. We formulate it as a constrained optimization problem and analyze its hardness. To address the problem, we propose algorithms to partition the entities into disjoint groups, and generate arithmetic constraints for each disjoint group separately. Then, the true attribute values of the entities in each disjoint group are derived by minimizing the objective function under the corresponding arithmetic constraints. Experimental results on both real-world and synthetic datasets demonstrate that the proposed approach achieves good performance even with very few constraints and reliable sources.

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. Our data structure uses $O(n (\log n \log\log n)^2)$ space, supports queries in worst case $O(\log^3 n)$ time, and updates in $O(\log^7 n)$ amortized time. This leads to an $O(n\alpha(n)\log^7 n)$ time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best $O(n^2)$ time algorithms., Comment: 14 pages, 7 figures

Problem definition: We consider an intermediary’s problem of dynamically matching demand and supply of heterogeneous types in a periodic-review fashion. Specifically, there are two disjoint sets of demand and supply types, and a reward for each possible matching of a demand type and a supply type. In each period, demand and supply of various types arrive in random quantities. The platform decides on the optimal matching policy to maximize the expected total discounted rewards, given that unmatched demand and supply may incur waiting or holding costs, and will be fully or partially carried over to the next period. Academic/practical relevance: The problem is crucial to many intermediaries who manage matchings centrally in a sharing economy. Methodology: We formulate the problem as a dynamic program. We explore the structural properties of the optimal policy and propose heuristic policies. Results: We provide sufficient conditions on matching rewards such that the optimal matching policy follows a priority hierarchy among possible matching pairs. We show that those conditions are satisfied by vertically and unidirectionally horizontally differentiated types, for which quality and distance determine priority, respectively. Managerial implications: The priority property simplifies the matching decision within a period, and the trade-off reduces to a choice between matching in the current period and that in the future. Then the optimal matching policy has a match-down-to structure when considering a specific pair of demand and supply types in the priority hierarchy.

In this paper, we define the operational and denotational semantics of a special class of parallel quantum programs, namely disjoint parallel quantum programs. Based on them, a proof system for reasoning about disjoint parallel quantum programs is developed, which is (relatively) complete even when entanglement between different processes appears in the preconditions and postconditions.

Funding: The first author is supported by an Engineering and Physical Sciences Research Council grant (EP/P015638/1). The second author is supported by a Royal Society University Research Fellowship (URF\R\180015). Let H ≤ Sn be an intransitive group with orbits Ω1, Ω2, ... , Ωk. Then certainly H is a subdirect product of the direct product of its projections on each orbit, H|Ω1 x H|Ω2 x ... x H|Ωk. Here we provide a polynomial time algorithm for computing the finest partition P of the H-orbits such that H = Πc∈P H|c and we demonstrate its usefulness in some applications. Postprint

Let $E$ be a rearrangement invariant (r.i.) function space on $[0,1]$, and let $Z_E$ consist of all measurable functions $f$ on $(0,\infty)$ such that $f^*\chi_{[0,1]}\in E$ and $f^*\chi_{[1,\infty)}\in L^2$. We reveal close connections between properties of the generalized Rosenthal's space, corresponding to the space $Z_E$, and the behaviour of independent symmetrically distributed random variables in $E$. The results obtained are applied to consider the problem of the existence of isomorphisms between r.i.\ spaces on $[0,1]$ and $(0,\infty)$. Exploiting particular properties of disjoint sequences, we identify a rather wide new class of r.i.\ spaces on $[0,1]$ ``close'' to $L^\infty$, which fail to be isomorphic to r.i.\ spaces on $(0,\infty)$. In particular, this property is shared by the Lorentz spaces $\Lambda_2(\log^{-\alpha}(e/u))$, with $0, Comment: submitted

In the area of change detection, there were a rare number of optimization methods. Most of the optimization methods that are used by change detection are morphological transformation or median filtering, which cannot best optimize change detection algorithm. In this paper, a general post-processing algorithm for change detection is proposed. We believe that some problems cannot be avoided in the area of change detection such as 1) region of moving object generated by change detection is slightly larger than the ground-truth and 2) there are always some disjoint and small regions that are independent from the moving objects. To address the problem, our method can optimize the change detection algorithm bases on the idea of edge detection, which can remove the wrong edge or pixel. In the experiments, more than 20 change detection algorithms that include the best algorithm in ChangeDetection.net are selected. Most of these change detection algorithms are optimized by the proposed method on PWC, Precision, and FMeasure, where, our optimized algorithm named FgSegNet_v2 is better than all other algorithms in the CDnet. The best-optimized margin of PWC is 0.64, and the fast speed is 548FPS on CPU. Our approach can better resolve the afore-mentioned problems that cannot be avoided and is general and fast. The experiments can be reproduced with C++ on Github https://github.com/walty19950301/CDA-contour-optimizer.

One of most central issues in various interconnection networks of parallel and distributed systems is to find edge-disjoint paths concerned with an information transmission through links. It is universally acknowledged that an interconnection network can be modeled as an undirected simple graph G = ( V , E ) with processors and physical links between the processors represented as vertices and edges of the G, respectively. The studies on the edge-disjoint paths are closely related to the edge-connectivity. By the well-known Menger theorem, the maximum number of edge disjoint paths connecting any two disjoint connected subgraphs with g vertices in G can also define by the minimum modified edge-cut, called the g-extra edge-connectivity of G λ g ( G ) . It is the cardinality of the minimum set of edges in G, if such a set exists, whose deletion disconnects G and leaves every remaining component with at least g vertices. The k-ary n-cube network is known as one of the most attractive interconnection networks for parallel and distributed systems. This article intends to show that for 3 ⌈ n 2 ⌉ + r − ⌊ 3 2 r + e + 1 2 ⌋ ≤ g ≤ 3 ⌈ n 2 ⌉ + r , the g-extra edge-connectivity of ternary n-cube (also called 3-ary n-cube) ( n ≥ 3 ) exists a concentration behavior, and prove that these corresponding g-extra edge-connectivities of ternary n-cubes are the constants 2 ( ⌊ n 2 ⌋ − r ) 3 ⌈ n 2 ⌉ + r , where r = 0 , 1 , 2 , ⋯ , ⌊ n 2 ⌋ − 1 , and e = 1 if n is odd and e = 0 if n is even. The above upper and lower bounds of g are sharp. As the integer g varies within the range between 3 ⌈ n 2 ⌉ + r − ⌊ 3 2 r + e + 1 2 ⌋ and 3 ⌈ n 2 ⌉ + r , a necessary and sufficient condition of λ g -optimality is found. Our results improve the several previous results.

We develop the Gompf fiber connected sum operation for symplectic orbifolds. We use it to construct a symplectic 4-orbifold with b 1 = 0 {b_{1}=0} and containing symplectic surfaces of genus 1 and 2 that are disjoint and span the rational homology. This is used in turn to construct a K-contact Smale–Barden manifold with specified 2-homology that satisfies the known topological constraints with sharper estimates than the examples constructed previously. The manifold can be chosen spin or non-spin.

V. V. Grushin and V. P. Palamodov proved in 1962 that it is impossible to place in [Formula: see text] uncountably many pairwise disjoint polyhedra each homeomorphic to the Moebius band. We generalize this result in two directions. First, we give a generalization of this result to tame subsets in [Formula: see text], [Formula: see text]. Second, we show that in case of [Formula: see text] the theorem holds for arbitrarily topologically embedded (not necessarily tame) Moebius bands.

During peak-hour busy airports have the challenge of turning aircraft around as quickly as possible, which includes sequencing their landings and take-offs with maximum efficiency, without sacrificing safety. This problem, termed aircraft sequencing problem (ASP) has traditionally been hard to solve optimally in real-time, even for flights over a one-hour planning window. In this article, we present a novel data-splitting algorithm to solve the ASP on a single runway with the objective to minimize the total delay in the system both under segregated and mixed mode of operation. The problem is formulated as a 0–1 mixed integer program, taking into account several realistic constraints, including safety separation standards, wide time-windows, and constrained position shifting. Following divide-and-conquer paradigm, the algorithm divides the given set of flights into several disjoint subsets, each of which is optimized using 0–1 MIP while ensuring the optimality of the entire set. One hour peak-traffic instances of this problem, which is NP-hard in general, are computationally difficult to solve with direct application of the commercial solver, as well as existing state-of-the-art dynamic programming method. Using our data-splitting algorithm, various randomly generated instances of the problem can be solved optimally in near real-time, with time savings of over 90%. Civil Aviation Authority of Singapore (CAAS) Nanyang Technological University This research has been partially supported under ATMRI (NTU-CAAS) Grant No. M4061216.

For fixed $r\geq 3$ and $n$ divisible by $r$, let ${\mathcal H}={\mathcal H}^r_{n,M}$ be the random $M$-edge $r$-graph on $V=\{1,\ldots ,n\}$; that is, ${\mathcal H}$ is chosen uniformly from the $M$-subsets of ${\mathcal K}:={V \choose r}$ ($:= \{\mbox{$r$-subsets of $V$}\}$). Shamir's Problem (circa 1980) asks, roughly, for what $M=M(n)$ is ${\mathcal H}$ likely to contain a perfect matching (that is, $n/r$ disjoint $r$-sets)? In 2008 Johansson, Vu and the author showed that this is true for $M>C_rn\log n$. More recently the author proved the asymptotically correct version of that result: for fixed $C> 1/r$ and $M> Cn\log n$, $P({\mathcal H} ~\mbox{contains a perfect matching})\rightarrow 1 \,\,\, \mbox{as $n\rightarrow\infty$}.$ The present work completes a proof, begun in that recent paper, of the definitive "hitting time" statement: $\mbox{Theorem.}$ If $A_1, \ldots ~$ is a uniform permutation of ${\mathcal K}$, ${\mathcal H}_t=\{A_1\dots A_t\}$, and \[ T=\min\{t:A_1\cup \cdots\cup A_t=V\}, \] then $P({\mathcal H}_T ~\mbox{contains a perfect matching})\rightarrow 1 \,\,\, \mbox{as $n\rightarrow\infty$}$.

Zero-Shot Learning (ZSL) has gained growing attention over the past few years mostly because it provides a significant scalability to recognition models for classifying instances from new unobserved classes. This scalability is achieved by providing semantic information about new classes, which could be obtained remarkably easier with lower cost, compared to collecting a new training set. Because seen and unseen classes are completely disjoint, ZSL methods often suffer from domain shift problem that occurs in transferring the knowledge of seen classes to unseen ones. Moreover, hubness problem that usually arises in high-dimensional space is another challenge in most ZSL methods due to applying nearest neighbor search for classification. To address these issues, a kernelized distance function is learned in order to discriminate the classes with a customized large-margin loss function. Furthermore, a simple theoretical-based prototype learning approach is provided by defining a non-linear mapping function to learn the visual prototype of each class from associated semantic information. For classification task, the learned distance function is utilized to measure the distance between instances and class-related prototypes. The evaluation on five benchmarks demonstrates the superiority of the proposed method over the state-of-the-art approaches in both zero-shot and generalized zero-shot learning problems.

Aharoni and Howard, and, independently, Huang, Loh, and Sudakov proposed the following rainbow version of Erd\H{o}s matching conjecture: For positive integers $n,k,m$ with $n\ge km$, if each of the families $F_1,\ldots, F_m\subseteq {[n]\choose k}$ has size more than $\max\{\binom{n}{k} - \binom{n-m+1}{k}, \binom{km-1}{k}\}$, then there exist pairwise disjoint subsets $e_1,\dots, e_m$ such that $e_i\in F_i$ for all $i\in [m]$. We prove that there exists an absolute constant $n_0$ such that this rainbow version holds for $k=3$ and $n\geq n_0$. We convert this rainbow matching problem to a matching problem on a special hypergraph $H$. We then combine several existing techniques on matchings in uniform hypergraphs: find an absorbing matching $M$ in $H$; use a randomization process of Alon et al. to find an almost regular subgraph of $H-V(M)$; and find an almost perfect matching in $H-V(M)$. To complete the process, we also need to prove a new result on matchings in 3-uniform hypergraphs, which can be viewed as a stability version of a result of {\L}uczak and Mieczkowska and might be of independent interest., Comment: added two references [2,7], accepted for publication in SCIENCE CHINA Mathematics

In set theory without the Axiom of Choice ( $\mathsf {AC}$ ), we investigate the open problem of the deductive strength of statements which concern the existence of almost disjoint and maximal almost disjoint (MAD) families of infinite-dimensional subspaces of a given infinite-dimensional vector space, as well as the extension of almost disjoint families in infinite-dimensional vector spaces to MAD families.

We investigate the emergence of spanning structures in sparse pseudo-random $k$-uniform hypergraphs, using the following comparatively weak notion of pseudo-randomness. A $k$-uniform hypergraph $H$ on $n$ vertices is called $(p,\alpha,\epsilon)$-pseudo-random if for all (not necessarily disjoint) vertex subsets $A_1,\dots, A_k{\subseteq} V(H)$ with $|A_1|\cdots |A_k|{\geq}\alpha n^{k}$ we have $$e(A_1,\dots, A_k)=(1\pm\epsilon)p |A_1|\cdots |A_k|.$$ For any linear $k$-uniform $F$ we provide a bound on $\alpha=\alpha(n)$ in terms of $p=p(n)$ and $F$, such that (under natural divisibility assumptions on $n$) any $k$-uniform $\big(p,\alpha, o(1)\big)$-pseudo-random $n$-vertex hypergraph $H$ with a mild minimum vertex degree condition contains an $F$-factor. The approach also enables us to establish the existence of loose Hamilton cycles in sufficiently pseudo-random hypergraphs and all results imply corresponding bounds for stronger notions of hypergraph pseudo-randomness such as jumbledness or large spectral gap. As a consequence, $\big(p,\alpha, o(1)\big)$-pseudo-random $k$-graphs as above contain: $(i)$ a perfect matching if $\alpha=o(p^{k})$ and $(ii)$ a loose Hamilton cycle if $\alpha=o(p^{k-1})$. This extends the works of Lenz--Mubayi, and Lenz--Mubayi--Mycroft who studied the analogous problems in the dense setting.

Anchor-based techniques reduce the computational complexity of spectral clustering algorithms. Although empirical tests have shown promising results, there is currently a lack of theoretical support for the anchoring approach. We define a specific anchor-based algorithm and show that it is amenable to rigorous analysis, as well as being effective in practice. We establish the theoretical consistency of the method in an asymptotic setting where data is sampled from an underlying continuous probability distribution. In particular, we provide sharp asymptotic conditions for the number of nearest neighbors in the algorithm, which ensure that the anchor-based method can recover with high probability disjoint clusters that are mutually separated by a positive distance. We illustrate the performance of the algorithm on synthetic data and explain how the theoretical convergence analysis can be used to inform the practical choice of parameter scalings. We also test the accuracy and efficiency of the algorithm on two large scale real data sets. We find that the algorithm offers clear advantages over standard spectral clustering. We also find that it is competitive with the state-of-the-art LSC method of Chen and Cai (Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011), while having the added benefit of a consistency guarantee.

Semi-bent functions play an important role in symmetric ciphers and sequence designs. So far, there are few studies related to the construction of vectorial semi-bent functions even though lots of work has been done on single-output semi-bent functions. In this paper, three classes of balanced vectorial semi-bent functions are presented with varying cryptographic properties. The classes denoted $${{\mathcal {D}}}{{\mathcal {C}}}$$ and $${{\mathcal {D}}}{{\mathcal {S}}}$$ are constructed using disjoint codes and disjoint spectra functions, respectively. The former class has a useful provable property that its component functions do not admit linear structures. It is shown that the number of output bits of the constructed n-variable $${{\mathcal {D}}}{{\mathcal {C}}}$$ and $${{\mathcal {D}}}{{\mathcal {S}}}$$ vectorial functions can respectively reach $$(n+1)/2$$ and n/3. In addition, a construction method of semi-bent functions from $${\mathbb {F}}_2^{3n} \rightarrow {\mathbb {F}}_2^n$$ by using almost bent (AB) functions on $${\mathbb {F}}_2^n$$ is given.

A simple $$(2,3,v)$$ trade is a pair $$(T_0,T_1)$$ of disjoint sets of $$3$$ -subsets (blocks) of a $$v$$ -set such that any two elements meet the same number of times in the blocks of $$T_0$$ and the blocks of $$T_1$$ . The size of $$T_0$$ equals the size of $$T_1$$ and is called the volume of the trade. In this paper, for $$v=4n+2$$ , we introduce a new partitioning of the set of all 3-subsets of a v-set into the trades of volume $$4$$ , $$6$$ , and $$8$$ .

We investigate the time evolution of odd entanglement entropy (OEE) and logarithmic negativity (LN) for the thermofield double (TFD) states in free scalar quantum field theories using the covariance matrix approach. To have mixed states, we choose non-complementary subsystems, either adjacent or disjoint intervals on each side of the TFD. We find that the time evolution pattern of OEE is a linear growth followed by saturation. On a circular lattice, for longer times the finite size effect demonstrates itself as oscillatory behavior. In the limit of vanishing mass, for a subsystem containing a single degree of freedom on each side of the TFD, we analytically find the effect of zero-mode on the time evolution of OEE which leads to logarithmic growth in the intermediate times. Moreover, for adjacent intervals we find that the LN is zero for times $t < \beta/2$ (half of the inverse temperature) and after that, it begins to grow linearly. For disjoint intervals at fixed temperature, the vanishing of LN is observed for times $t, Comment: 44 pages, 17 figures, Comments about memory effect and some references are added

In automotive manufacturing, production systems typically involve multiple robots and, today, are being individualized by utilizing the concept of digital twins. Therefore, the robot programs need to be verified for each individual product. A crucial aspect is to avoid collisions between robots by velocity tuning: This involves an efficient analysis of pairs of robot paths and determining if swept volumes of (sub) paths are disjoint. In general, velocity uncertain motions require disjoint sweep volumes to be safe. We optimize a clearance lower bounding function to provide new sample points for clearance computations. Due to the computational cost of each distance query, our sampling strategy aims to maximize the information gained at each query. The algorithm terminates when robot paths are verified to be disjoint or a collision is detected. Our approach for disjoint paths is inspired by the technique for continuous collision detection known as conservative advancement . Our tests indicate that the proposed sampling method is reliable and computationally much faster than creating and intersecting octrees representing the swept volumes.

Software defined network (SDN) is a new modern network technology which decouples control plane and data plane to simplify network management. The separation of control plane from data plane arises the control placement problem (CPP) in these networks. The main questions in the CPP are (1) how many controllers are required to be used in such networks and (2) where these controllers should be placed. To achieve an efficient solution for such problem in SDN, we define the CPP as a multi-objective combinational optimization problem in this paper and solve the CPP by applying the antlion optimization algorithm on it. We consider three metrics for the CPP: (a) Inter-controllers latency, (b) switch to controller latency, and (c) multiple disjoint connectivity paths between switches and controllers. We evaluate our proposed solution by performing several experiments using different real network topologies. Experimental results show that our proposed solution provides better performance compared to the existing solutions.

Phylogenetic trees are representations of the evolutionary descendency of a set of species. In graph-theoretic terms, a phylogenetic tree is a partially labeled tree where unlabeled vertices have at least degree three and labels corresponds to pairwise disjoint subsets of the set of species. A cut of a graph G = (V, E) is defined as bipartition {S, V \ S} of the vertex set V of G. A pair of cuts {S, S}, {T, T} is said to be crossing, if neither S ∩ T, S ∩ T, S ∩ T nor S ∩ T is empty. In this paper, we show that each set of pairwise non-crossing cuts of a graph G can be represented uniquely by a phylogenetic tree such that the set of species corresponds to the vertex set of G.

A complex K3 surface or an algebraic K3 surface in characteristics distinct from $2$ cannot have more than $16$ disjoint nodal curves., A complex K3 surface or an algebraic K3 surface in characteristics distinct from 2 cannot have more than 16 disjoint nodal curves.

Reversible Cellular Automata (RCA) are a particular kind of shift-invariant transformations characterized by a dynamics composed only of disjoint cycles. They have many applications in the simulation of physical systems, cryptography and reversible computing. In this work, we formulate the search of a specific class of RCA -- namely, those whose local update rules are defined by conserved landscapes -- as an optimization problem to be tackled with Genetic Algorithms (GA) and Genetic Programming (GP). In particular, our experimental investigation revolves around three different research questions, which we address through a single-objective, a multi-objective, and a lexicographic approach. The results obtained from our experiments corroborate the previous findings and shed new light on 1) the difficulty of the associated optimization problem for GA and GP, 2) the relevance of conserved landscape CA in the domain of cryptography and reversible computing, and 3) the relationship between the reversibility property and the Hamming weight., Comment: 39 pages, 12 figures, 2 tables, pre-print of an extension of a paper published in EuroGP 2020

For a separable rearrangement invariant space X on $$(0,\infty )$$ of fundamental type we identify the set of all $$p\in [1,\infty ]$$ such that $$\ell ^p$$ is finitely represented in X in such a way that the unit basis vectors of $$\ell ^p$$ ( $$c_0$$ if $$p=\infty $$ ) correspond to pairwise disjoint and equimeasurable functions. This characterization hinges upon a description of the set of approximate eigenvalues of the doubling operator $$x(t)\mapsto x(t/2)$$ in X. We prove that this set is surprisingly simple: depending on the values of some dilation indices of such a space, it is either an interval or a union of two intervals. We apply these results to the Lorentz and Orlicz spaces.

The Satisfiability Modulo Theories (SMT) issue concerns the satisfiability of formulae from multiple background theories, usually expressed in the language of first-order predicate logic with equality. SMT solvers are often based on variants of the Nelson-Oppen combination method, a solver for the quantifier-free fragment of the combination of theories with disjoint signatures, via cooperation among their decision procedures. When each of the theories to be combined by the Nelson-Oppen method is convex (that is, any conjunction of its literals can imply a disjunction of equalities only when it implies at least one of the equalities) and decidable in polynomial time, the running time of the combination procedure is guaranteed to be polynomial in the size of the input formula. In this paper, we prove the convexity of a fragment of Zermelo-Fraenkel set theory, called Multi-Level Syllogistic, most of whose polynomially decidable fragments we have recently characterized., In Proceedings GandALF 2021, arXiv:2109.07798

Given an undirected connected graph G = ( V , E ) with vertex set V and edge set E, the minimum conductance graph partitioning problem is to partition V into two disjoint subsets such that the conductance, i.e., the ratio of the number of cut edges to the smallest volume of two partition subsets is minimized. This problem has a number of practical applications in various areas such as community detection, bioinformatics , and computer vision . However, the problem is computationally challenging, especially for large problem instances. This work presents the first iterated multilevel simulated annealing algorithm for large-scale graph conductance minimization. The algorithm features a novel solution-guided coarsening method and an effective solution refinement procedure based on simulated annealing. Computational experiments demonstrate the high performance of the algorithm on 66 very large real-world sparse graphs with up to 23 million vertices. Additional experiments are presented to get insights into the influences of its algorithmic components . The source code of the proposed algorithm is publicly available, which can be used to solve various real world problems .

We continue our study of bounded solutions of the semilinear parabolic equation u t = u x x + f ( u ) on the real line, where f is a locally Lipschitz function on R . Assuming that the initial value u 0 = u ( ⋅ , 0 ) of the solution has finite limits θ ± as x → ± ∞ , our goal is to describe the asymptotic behavior of u ( x , t ) as t → ∞ . In a prior work, we showed that if the two limits are distinct, then the solution is quasiconvergent, that is, all its locally uniform limit profiles as t → ∞ are steady states. It is known that this result is not valid in general if the limits are equal: θ ± = θ 0 . In the present paper, we have a closer look at the equal-limits case. Under minor non-degeneracy assumptions on the nonlinearity, we show that the solution is quasiconvergent if either f ( θ 0 ) ≠ 0 , or f ( θ 0 ) = 0 and θ 0 is a stable equilibrium of the equation ξ ˙ = f ( ξ ) . If f ( θ 0 ) = 0 and θ 0 is an unstable equilibrium of the equation ξ ˙ = f ( ξ ) , we also prove some quasiconvergence theorem making (necessarily) additional assumptions on u 0 . A major ingredient of our proofs of the quasiconvergence theorems—and a result of independent interest—is the classification of entire solutions of a certain type as steady states and heteroclinic connections between two disjoint sets of steady states.

Clustering is performed to partition samples into disjoint groups for facilitating the discovery of hidden patterns in the data. Many real-world applications involve various clustering methods , most of which only produce a single clustering. As a response to this issue, multiple clustering that aims to generate diverse and high-quality clustering, has emerged recently. This study proposes a novel autoencoder-like semi-nonnegative matrix factorization (NMF) multiple clustering (ASNMFMC) model that generates multiple non-redundant, high-quality clustering. The nonnegative property of the semi-NMF is utilized by the algorithm to enforce non-redundancy. Extensive experimental results demonstrate that the ASNMFMC is superior to the existing multiple clustering methods and can explore diverse high-quality clustering.

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never use the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. On the one extreme, we show that on general graphs the problem is computationally hard. The "walk version" is W[1]-hard when parameterized by the number of routes. However, it is polynomial-time solvable for any constant number of walks. The "path version" remains NP-hard even if we want to find only two temporally disjoint paths. On the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counterintuitively, we find NP-hardness in general but also identify natural tractable cases.

Graph partitioning has been studied in the discipline between computer science and applied mathematics. It is a technique to distribute the whole graph data as a disjoint subset to a different device. The minimum graph partition problem with respect to an independence system of a graph has been studied in this paper. The considered independence system consists of one of the independent sets defined by Boutin. We solve the minimum partition problem in path graphs, cycle graphs, and wheel graphs. We supply a relation of twin vertices of a graph with its independence system. We see that a maximal independent set is not always a minimal set in some situations. We also provide realizations about the maximum cardinality of a minimum partition of the independence system. Furthermore, we study the comparison of the metric dimension problem of a graph with the minimum partition problem of that graph.

Let $V$ be a regular neighborhood of a negative chain of $2$-spheres (i.e. exceptional divisor of a cyclic quotient singularity), and let $B_{p,q}$ be a rational homology ball which is smoothly embedded in $V$. Assume that the embedding is simple, i.e. the corresponding rational blow-up can be obtained by just a sequence of ordinary blow-ups from $V$. Then we show that this simple embedding comes from the semi-stable minimal model program (MMP) for $3$-dimensional complex algebraic varieties under certain mild conditions. That is, one can find all simply embedded $B_{p,q}$'s in $V$ via a finite sequence of antiflips applied to a trivial family over a disk. As applications, simple embeddings are impossible for chains of $2$-spheres with self-intersections equal to $-2$. We also show that there are (infinitely many) pairs of disjoint $B_{p,q}$'s smoothly embedded in regular neighborhoods of (almost all) negative chains of $2$-spheres. Along the way, we describe how MMP gives (infinitely many) pairs of disjoint rational homology balls $B_{p,q}$ embedded in blown-up rational homology balls $B_{n,a} # \bar{\mathbb{CP}^2}$ (via certain divisorial contractions), and in the Milnor fibers of certain cyclic quotient surface singularities. This generalizes results in [Khodorovskiy-2014], [H. Park-J. Park-D. Shin-2016], [Owens-2017] by means of a uniform point of view., Comment: 16 pages

At every point, a smooth plane curve can be approximated, to second order, by a circle; this circle is called osculating. One may think of the osculating circle as passing through three infinitesimally close points of the curve. A vertex of the curve is a point at which the osculating circle hyper-osculates: it approximates the curve to third order. Equivalently, a vertex is a critical point of the curvature function. Consider a (necessarily non-closed) curve, free from vertices. The classical Tait-Kneser theorem [13, 5] (see also [3, 10]), states that the osculating circles of the curve are pairwise disjoint, see Figure 1. This theorem is closely related to the four vertex theorem of S. Mukhopadhyaya [8] that a plane oval has at least 4 vertices (see again [3, 10]). Figure 1 illustrates the Tait-Kneser theorem: it shows an annulus foliated by osculating circles of a curve.

The parameters of a $q$ -ary MDS Euclidean self-dual codes are completely determined by its length and the construction of MDS Euclidean self-dual codes with new length has been widely investigated in recent years. In this paper, we give a further study on the construction of MDS Euclidean self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The main idea of our construction is to choose suitable evaluation points such that the corresponding (extended) GRS codes are Euclidean self-dual. Firstly, we consider the evaluation set consists of two disjoint subsets, one of which is based on the trace function, the other one is a union of a subspace and its cosets. Then four new families of MDS Euclidean self-dual codes are constructed. Secondly, we give a simple but useful lemma to ensure that the symmetric difference of two intersecting subsets of finite fields can be taken as the desired evaluation set. Based on this lemma, we generalize our first construction and provide two new families of MDS Euclidean self-dual codes. Finally, by using two multiplicative subgroups and their cosets which have nonempty intersection, we present three generic constructions of MDS Euclidean self-dual codes with flexible parameters. Several new families of MDS Euclidean self-dual codes are explicitly constructed.

Given a connected graph G and S ⊆ V ( G ) with | S | ≥ 2 , a tree T in G is called an S-Steiner tree (or S-tree for short) if S ⊆ V ( T ) . Two S-trees T 1 and T 2 are internally disjoint if E ( T 1 ) ∩ E ( T 2 ) = ∅ and V ( T 1 ) ∩ V ( T 2 ) = S . The packing number of internally disjoint S-trees, denoted as κ G ( S ) , is the maximum size of a set of internally disjoint S-trees in G. For an integer k ≥ 2 , the generalized k-connectivity (abbr. κ k -connectivity) of a graph G is defined as κ k ( G ) = min { κ G ( S ) | S ⊆ V ( G ) and | S | = k } . The n-dimensional augmented cube, denoted as A Q n , is an important variant of the hypercube that possesses several desired topology properties such as diverse embedding schemes in applications of parallel computing. In this paper, we focus on the study of constructing internally disjoint S-trees with | S | = 3 in A Q n . As a result, we completely determine the κ 3 -connectivity of A Q n as follows: κ 3 ( A Q 4 ) = 5 and κ 3 ( A Q n ) = 2 n − 2 for n = 3 or n ≥ 5 .

This paper examines the conjoint/disjoint alternation in matrix verbs which take clausal complements in Zulu. It shows that the typical verbs which by default take the disjoint form with a clausal complement are factive verbs, though it is also clear that other attitude verbs can undergo the conjoint/disjoint alternation as well. The paper explores the connection between focus and the conjoint/disjoint alternation in Zulu utilising the Question Under Discussion (QUD) approach. This will help to understand the interpretations associated with the alternations in combination with clausal complements.

We analyse the eigenvectors of the adjacency matrix of a critical Erdős–Rényi graph $${\mathbb {G}}(N,d/N)$$ G ( N , d / N ) , where d is of order $$\log N$$ log N . We show that its spectrum splits into two phases: a delocalized phase in the middle of the spectrum, where the eigenvectors are completely delocalized, and a semilocalized phase near the edges of the spectrum, where the eigenvectors are essentially localized on a small number of vertices. In the semilocalized phase the mass of an eigenvector is concentrated in a small number of disjoint balls centred around resonant vertices, in each of which it is a radial exponentially decaying function. The transition between the phases is sharp and is manifested in a discontinuity in the localization exponent $$\gamma (\varvec{\mathrm {w}})$$ γ ( w ) of an eigenvector $$\varvec{\mathrm {w}}$$ w , defined through $$\Vert \varvec{\mathrm {w}} \Vert _\infty / \Vert \varvec{\mathrm {w}} \Vert _2 = N^{-\gamma (\varvec{\mathrm {w}})}$$ ‖ w ‖ ∞ / ‖ w ‖ 2 = N - γ ( w ) . Our results remain valid throughout the optimal regime $$\sqrt{\log N} \ll d \leqslant O(\log N)$$ log N ≪ d ⩽ O ( log N ) .

In this article, we give two different sufficient conditions for the irreducibility of a polynomial of more than one variable, over the field of complex numbers, that can be written as a sum of two polynomials which depend on mutually disjoint sets of variables. These conditions are derived from analyzing the Newton polytope of such a polynomial and then applying the `Irreducibility criterion' introduced by Gao., 10 pages, minor change in the statement of Proposition 1.4 and the proof of the same is rewritten for clarity, to appear in Indian Journal of Pure and Applied Mathematics

The set of points where an entire function achieves its maximum modulus is known as the maximum modulus set. In 1951, Hayman studied the structure of this set near the origin. Following work of Blumenthal, he showed that, near zero, the maximum modulus set consists of a collection of disjoint analytic curves, and provided an upper bound for the number of these curves. In this paper, we establish the exact number of these curves for all entire functions, except for a "small" set whose Taylor series coefficients satisfy a certain simple, algebraic condition. Moreover, we give new results concerning the structure of this set near the origin, and make an interesting conjecture regarding the most general case. We prove this conjecture for polynomials of degree less than four., Comment: 15 pages, 1 figure. V2: minor additional clarifications included

The piecewise monotonic approximation problem makes the least changes to n univariate noisy data so that the piecewise linear interpolant to the new values is composed of at most k monotonic sections. The term “least changes” is defined in the sense of a global sum of strictly convex functions of changes. The main difficulty in this calculation is that the extrema of the interpolant have to be found automatically, but the number of all possible combinations of extrema can be $${\mathcal {O}}(n^{k-1})$$ , which makes not practicable to test each one separately. It is known that the case $$k=1$$ is straightforward, and that the case $$k>1$$ reduces to partitioning the data into at most k disjoint sets of adjacent data and solving a $$k=1$$ problem for each set. Some ordering relations of the extrema are studied that establish three quite efficient algorithms by using a binary search method for partitioning the data. In the least squares case the total work is only $${\mathcal {O}}(n \sigma +k\sigma \log _2\sigma )$$ computer operations when $$k \ge 3$$ and is only $${\mathcal {O}}(n)$$ when $$k=1$$ or 2, where $$\sigma -2$$ is the number of sign changes in the sequence of the first differences of the data. Fortran software has been written for this case and the numerical results indicate superior performance to existing algorithms. Some examples with real data illustrate the method. Many applications of the method arise from bioinformatics, energy, geophysics, medical imaging, and peak finding in spectroscopy, for instance.