Search

The Hirota variety parameterizes solutions to the KP equation arising from a degenerate Riemann theta function. In this work, we study in detail the Hirota variety arising from a rational nodal curve. Of particular interest is the irreducible subvariety defined as the image of a parameterization map, we call this the main component. Proving that this is an irreducible component of the Hirota variety corresponds to solving a weak Schottky problem for rational nodal curves. We solve this problem up to genus nine using computational tools. [ABSTRACT FROM AUTHOR]

In the context of reconstructing phylogenetic networks from a collection of phylogenetic trees, several characterisations and subsequently algorithms have been established to reconstruct a phylogenetic network that collectively embeds all trees in the input in some minimum way. For many instances however, the resulting network also embeds additional phylogenetic trees that are not part of the input. However, little is known about these inferred trees. In this paper, we explore the relationships among all phylogenetic trees that are embedded in a given phylogenetic network. First, we investigate some combinatorial properties of the collection P of all rooted binary phylogenetic trees that are embedded in a rooted binary phylogenetic network N. To this end, we associated a particular graph G , which we call rSPR graph, with the elements in P and show that, if | P | = 2 k , where k is the number of vertices with in-degree two in N , then G has a Hamilton cycle. Second, by exploiting rSPR graphs and properties of hypercubes, we turn to the well-studied class of rooted binary level-1 networks and give necessary and sufficient conditions for when a set of rooted binary phylogenetic trees can be embedded in a level-1 network without inferring any additional trees. Lastly, we show how these conditions translate into a polynomial-time algorithm to reconstruct such a network if it exists. [ABSTRACT FROM AUTHOR]

In 1992, Bagga, Beineke, and Varma introduced the concept of the super line graph of index of a graph denoted by The vertices of are the -subsets of and two vertices and are adjacent if there exist and such that and are adjacent edges in They also defined the line completion number of graph G to be the minimum index for which is complete. They found the line completion number for certain classes of graphs. In this paper, we find the line completion number of hypercube for every .

The Cartesian product of n cycles is a 2n-regular, 2n-connected and bi- pancyclic graph. Let G be the Cartesian product of n even cycles and let 2n = n1+ n2+ ・ ・ ・ + nkwith k ≥ 2 and ni≥ 2 for each i. We prove that if k = 2, then G can be decomposed into two spanning subgraphs G1and G2such that each Giis ni-regular, ni-connected, and bipancyclic or nearly bipancyclic. For k > 2, we establish that if all niin the partition of 2n are even, then G can be decomposed into k spanning subgraphs G1,G2, . . . ,Gk such that each Giis ni-regular and ni-connected. These results are analo- gous to the corresponding results for hypercubes.

Two vertices of the k-dimensional hypercube Qkare antipodal if they differ in every coordinate. Edges uv and xy are antipodal if u is antipodal to x and v is antipodal to y. An antipodal edge-coloring of Qkis a 2- edge-coloring such that antipodal edges always have different colors. Norine conjectured that for k ≥ 2, in every antipodal edge-coloring of Qksome two antipodal vertices are connected by a monochromatic path. Feder and Subi proved this for k ≤ 5. We prove it for k ≤ 6.

The concept of conformal transformation is proposed through the study of the spatial structure of n -dimensional hypercubes. Based on conformal transformation, a novel algorithm, called topological equivalence classification algorithm, is proposed for classifying balanced linearly separable Boolean functions. By the proposed algorithm, the topological equivalence classes of all balanced linearly separable Boolean functions and the number of Boolean functions in each of the topological equivalence classes are obtained. In addition, the properties of conformal transformation also show an application prospect for decomposing nonlinearly separable Boolean functions. [ABSTRACT FROM AUTHOR]

Reliability measure of multiprocessor systems is of significant importance to the design and maintenance of multiprocessor systems. Based on edge connectivity, more refined quantitative indicators for the reliability of multiprocessor systems have been introduced. The extra edge connectivity and the component edge connectivity, as two important parameters to evaluate the robustness of multiprocessor systems, are explored extensively. In this paper, we first determine the h -extra edge connectivity of the enhanced hypercube Q n , k (one potential alternative of hypercube) for 1 ≤ h ≤ 2 ⌈ n 2 ⌉ + 1 , n ≥ 2 k + 4 and 1 ≤ h ≤ 2 ⌈ n 2 ⌉ , n ≤ 2 k + 3 , k ≥ 3. Some previous results in Zhang et al. (2016) and Sabir et al. (2019) are extended. Moreover, we also establish the g -component edge connectivity of the n -dimensional enhanced hypercube Q n , k for 1 ≤ g ≤ 2 ⌈ n 2 ⌉ + 1 , n ≥ 13. As an easy extension, similar results for folded hypercube F Q n , another popular network structure, are readily derived. [ABSTRACT FROM AUTHOR]

The g -good-neighbor conditional diagnosability, which specifies at least g fault-free neighbors for each fault-free node, is a very important metric in system-level diagnosis. Recently, the g -good-neighbor conditional diagnosabilities of many networks have been investigated. To enhance the g -good-neighbor conditional diagnosability, the R g -conditional diagnosability, which requires at least g fault-free neighbors for each node, has been proposed by Guo et al. [1] (2020) recently. And they establish the R g -conditional diagnosability of the hypercubes under the PMC model. In this paper, we present some counterexamples for the proof of lower bound on the R g -conditional diagnosability of the hypercubes under the PMC model, which is crucial to the original main result. And we further utilize known results to give a reasonable lower bound for the R g -conditional diagnosability of hypercubes. [ABSTRACT FROM AUTHOR]

Set functions are functions (or signals) indexed by the powerset (set of all subsets) of a finite set N. They are fundamental and ubiquitous in many application domains and have been used, for example, to formally describe or quantify loss functions for semantic image segmentation, the informativeness of sensors in sensor networks the utility of sets of items in recommender systems, cooperative games in game theory, or bidders in combinatorial auctions. In particular, the subclass of submodular functions occurs in many optimization and machine learning problems. In this paper, we derive discrete-set signal processing (SP), a novel shift-invariant linear signal processing framework for set functions. Discrete-set SP considers different notions of shift obtained from set union and difference operations. For each shift it provides associated notions of shift-invariant filters, convolution, Fourier transform, and frequency response. We provide intuition for our framework using the concept of generalized coverage function that we define, identify multivariate mutual information as a special case of a discrete-set spectrum, and motivate frequency ordering. Our work brings a new set of tools for analyzing and processing set functions, and, in particular, for dealing with their exponential nature. We show two prototypical applications and experiments: compression in submodular function optimization and sampling for preference elicitation in combinatorial auctions. [ABSTRACT FROM AUTHOR]

The constructions of node-disjoint paths have been well applied to the study of connectivity, diameter, parallel routing, reliability, and fault tolerance of an interconnection network. In order to minimize the transmission cost and latency, the total length and maximal length of the node-disjoint paths should be minimized, respectively. The construction of node-disjoint paths with their maximal length minimized (in the worst case) has been studied previously in folded hypercubes. In this paper, we construct m node-disjoint paths from one source node to other m (not necessarily distinct) target nodes, respectively, in an n -dimensional folded hypercube so that both of their total length and maximal length (in the worst case) are minimized, where m ≤ n +1. In addition, each path is either shortest or nearly shortest. The construction of these node-disjoint paths can be efficiently carried out in O ( mn 1.5 + m 3 n) and O (mn 2 + n 2 log n + m 3 n) time, respectively, for odd and even n by taking advantage of two specific routing functions, which provide another strong evidence for the effective applications of routing functions in deriving node-disjoint paths, especially for the variants of hypercubes. • Constructing node-disjoint paths with total length minimized in folded hypercubes. • Routing functions are effective on constructing node-disjoint paths. • Finding maximum matchings can help to find node-disjoint paths. [ABSTRACT FROM AUTHOR]

In this paper, we study the fault-tolerant capability of hypercubes with respect to the hamiltonian property based on the concept of forbidden faulty sets. We show, with the assumption that each vertex is incident with at least three fault-free edges, that an n -dimensional hypercube contains a fault-free hamiltonian cycle, even if there are up to (4 n − 1 3) edge faults. Moreover, we give an example to show that the result is optimal with respect to the number of edge faults tolerated. [ABSTRACT FROM AUTHOR]

Let H be a connected subgraph of a connected graph G. The H-structure connectivity of the graph G, denoted by κ(G;H), is the minimum cardinality of a minimal set of subgraphs F={H1′,H2′,...,Hm′} in G, such that every Hi′∈F is isomorphic to H and removal of F from G will disconnect G. The H-substructure connectivity of the graph G, denoted by κs(G;H), is the minimum cardinality of a minimal set of subgraphs F={J1′,J2′,...,Jm′} in G, such that every Ji′∈F is a connected subgraph of H and removal of F from G will disconnect G. In this paper, we provide the H-structure and the H-substructure connectivity of the circulant graph Cir(n,Ω) where Ω={1,...,k,n-k,...,n-1},1≤k≤1/2 and the hypercube Qn for some connected subgraphs H. [ABSTRACT FROM AUTHOR]

The aim of this study is to compare the effect of two sampling patterns: systematic sampling and Latin hypercube sampling (LHS), on estimation precision of snow water equivalent (SWE), and also comparing different geostatistics methods of kriging, cokriging and radial basin functions for mapping SWE. To achieve the study purpose, the semi-arid mountainous watershed of Sohrevard in Zanjan Province of Iran was selected. Snow depth in 150 points with systematic sampling and 150 points with LHS sampling and snow density in 18 points were randomly measured. In addition, SWE was calculated in the study area, and its map was derived based on both the sampling methods using geostatistical techniques. The results showed that the accuracy of the SWE map using LHS was higher than systematic sampling. According to the most statistical indicators, in both methods of sampling, accuracy of mapping using regular spline was better than other methods. [ABSTRACT FROM AUTHOR]

A space bounded O (d / log d) -competitive hypercube packing algorithm with one active bin only is presented. As a starting point we give a simple 1-space bounded hypercube packing algorithm with competitive ratio (3 / 2) d + O ((21 / 16) d) , for d ≥ 3. [ABSTRACT FROM AUTHOR]

We consider the problem of extending partial edge colorings of hypercubes. In particular, we obtain an analogue of the positive solution to the famous Evans' conjecture on completing partial Latin squares by proving that every proper partial edge coloring of at most d−1 edges of the d‐dimensional hypercube Qd can be extended to a proper d‐edge coloring of Qd. Additionally, we characterize which partial edge colorings of Qd with precisely d precolored edges are extendable to proper d‐edge colorings of Qd. [ABSTRACT FROM AUTHOR]

A subset of vertices in a graph is called resolving when the geodesic distances to those vertices uniquely distinguish every vertex in the graph. Here, we characterize the resolvability of Hamming graphs in terms of a constrained linear system and deduce a novel but straightforward characterization of resolvability for hypercubes. We propose an integer linear programming method to assess resolvability rapidly and provide a more costly but definite method based on Grobner bases to determine whether or not a set of vertices resolves an arbitrary Hamming graph. As proof of concept, we identify a resolving set of size 77 in the metric space of all octapeptides (i.e., proteins composed of eight amino acids) with respect to the Hamming distance; in particular, any octamer may be readily represented as a 77-dimensional real vector. Representing k-mers as low-dimensional numerical vectors may enable new applications of machine learning algorithms to symbolic sequences. [ABSTRACT FROM AUTHOR]

The article introduces a general method of construction of asymmetrical regular factorial main-effect designs in 2 n runs. It presents a collection of optimal designs constructed by this method in 32, 64, 128, and 256 runs. The method provides exploration of design structure and construction of designs with required properties. Construction of composite designs is given as an example of design structure exploration. [ABSTRACT FROM AUTHOR]

An l1-graph is one in which the vertices can be labeled by binary vectors such that the Hamming distance between two binary addresses is, to scale, the distance in the graph between the corresponding vertices. This study was designed to determine whether the gate-sum operation can inherit the l1-embeddability. The subgraph H of a graph G is called a gate subgraph if, for every vertex v ∈ V(G), there exists a vertex x ∈ V(H) such that for every vertex u of H, x lies on a shortest path from v to u. The graph G is defined as the gate-sum of two graphs G1 and G2 with respect to H if H is a gate subgraph of at least one of G1 and G2, such that G1∪G2 = G, G1∩G2 = H, and both G1 and G2 are isometric subgraphs of G. In this article, we have shown that the gate-sum graph of two l1-graphs is also an l1-graph.

Hyperspectral imaging is currently a very well-known and much used technology for measuring features in different fields, such as chemistry, geology, medicine, food and agriculture, either spaceborne (satellites), airborne (drones) or at close proximity (e.g. field scanning, industrial sorting lines or microscopy). Its background is two-fold, and it can be considered as a special case of spectroscopy (“imaging spectroscopy”) or a special case of imaging (“spectral imaging”). Current practice is to use adjectives such as multi and hyper added to “spectral imaging” in order to characterise the number of wavelength bands. In this paper we propose the community to use scientifically sound terminology, like “imaging spectroscopy” or “spectral imaging”, without using ambiguous adjectives. Further, we encourage the community to define and agree upon clear adjectives to describe the number of variables in the naming of our imaging technique.

We live in a three-dimensional (3D) spatial world; however, our retinas receive a pair of 2D projections of the 3D environment. By using multiple cues, such as disparity, motion parallax, perspective, our brains can construct 3D representations of the world from the 2D projections on our retinas. These 3D representations underlie our 3D perceptions of the world and are mapped into our motor systems to generate accurate sensorimotor behaviors. Three-dimensional perceptual and sensorimotor capabilities emerge during development: the physiology of the growing baby changes hence necessitating an ongoing re-adaptation of the mapping between 3D sensory representations and the motor coordinates. This adaptation continues in adulthood and is quite general to successfully deal with joint-space changes (longer arms due to growth), skull and eye size changes (and still being able of accurate eye movements), etc. A fundamental question is whether our brains are inherently limited to 3D representations of the environment because we are living in a 3D world, or alternatively, our brains may have the inherent capability and plasticity of representing arbitrary dimensions; however, 3D representations emerge from the fact that our development and learning take place in a 3D world. Here, we review research related to inherent capabilities and limitations of brain plasticity in terms of its spatial representations and discuss whether with appropriate training, humans can build perceptual and sensorimotor representations of spatial 4D environments, and how the presence or lack of ability of a solid and direct 4D representation can reveal underlying neural representations of space.

The connectivity of a graph is an important measurement for the fault-tolerance of the network. To provide more accurate measures for the fault-tolerance of networks than the connectivity, some generalizations of connectivity have been introduced. Let be a connected subgraph of a graph . A set of a connected subgraphs of is called a subgraph cut of if is either disconnected or trivial. If further, each member of is isomorphic to , then is called an -structure cut of G. The -structure connectivity of is the minimum cardinality of an -structure cut of . In this paper we determine or its upper bound where is the -dimensional hypercube with and is either with or even cycle with .

Ruskey and Savage asked the following question: Does every matching in a hypercube Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n ∈ {2, 3, 4}. In this paper, we prove that every matching in Q5 can be extended to a Hamiltonian cycle of Q5.

Network cost is equal to degree × diameter and is one of the important measurements when evaluating graphs. Torus and hypercube are very well-known graphs. When these graphs expand, a Torus has an advantage in that its degree does not increase. A hypercube has a shorter diameter than that of other graphs, because when the graph expands, the diameter increases by 1. Hypercube Qn has 2n nodes, and its diameter is n. We propose the rotational binary graph (RBG), which has the advantages of both hypercube and Torus. RBGn has 2n nodes and a degree of 4. The diameter of RBGn would be 1.5n + 1. In this paper, we first examine the topology properties of RBG. Second, we construct a binary spanning tree in RBG. Third, we compare other graphs to RBG considering network cost specifically. Fourth, we suggest a broadcast algorithm with a time complexity of 2n − 2. Finally, we prove that RBGn embedded into hypercube Qn results in dilation n, and expansion 1, and congestion 7. [ABSTRACT FROM AUTHOR]

In this paper we disprove a result on the PBIB designs arising from γ bc -sets in Q 4 , with m = 4 association schemes proved by Chaluvaraju et al. (Afr Math 29:47–63, 2018). In Ref. [11], the authors had posed an open problem to find the PBIB designs in hypercubes of dimension higher than 5. Here, we settle the problem for the first few values, and give a general iterative proof technique for higher dimensional hypercubes. [ABSTRACT FROM AUTHOR]

Hypercubes and Fibonacci cubes are classical models for interconnection networks with interesting graph theoretic properties. We consider k -Fibonacci cubes, which we obtain as subgraphs of Fibonacci cubes by eliminating certain edges during the fundamental recursion phase of their construction. These graphs have the same number of vertices as Fibonacci cubes, but their edge sets are determined by a parameter k. We obtain properties of k -Fibonacci cubes including the number of edges, the average degree of a vertex, the degree sequence and the number of hypercubes they contain. [ABSTRACT FROM AUTHOR]

Fibonacci cubes are defined as subgraphs of hypercubes, where the vertices are those without two consecutive 1's in their binary string representation. k -Fibonacci cubes are in turn special subgraphs of Fibonacci cubes obtained by eliminating certain edges. This elimination is carried out at the step analogous to where the fundamental recursion is used to construct Fibonacci cubes themselves from the two previous cubes by link edges. In this work, we calculate the vertex chromatic polynomial of k -Fibonacci cubes for k = 1, 2. We also determine the domination number and the total domination number of k -Fibonacci cubes for n, k ≤ 12 by using an integer programming formulation. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with multivariate Gegenbauer approximation of functions defined in the d-dimensional hypercube. Two new and sharper bounds for the coefficients of multivariate Gegenbauer expansion of analytic functions are presented based on two different extensions of the Bernstein ellipse. We then establish an explicit error bound for the multivariate Gegenbauer approximation associated with an ℓq ball index set in the uniform norm. We also consider the multivariate approximation of functions with finite regularity and derive the associated error bound on the full grid in the uniform norm. As an application, we extend our arguments to obtain some new tight bounds for the coefficients of tensorized Legendre expansions in the context of polynomial approximation of parametrized PDEs. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of decomposing the augmented cube A Q n into two spanning, regular, connected and pancyclic subgraphs. We prove that for n ≥ 4 and 2 n − 1 = n 1 + n 2 with n 1 , n 2 ≥ 2 , A Q n can be decomposed into two spanning subgraphs H 1 and H 2 such that H i is n i -regular and n i -connected for i = 1 , 2. Moreover, H i is 4-pancyclic if n i ≥ 3. • In this paper we have given a decomposition of Augmented cube A Q n. • Decomposition gives us two spanning regular connected pancyclic subgraphs of A Q n. • Degrees of subgraphs are based on given 2-partition of 2 n − 1 which is the degree of A Q n . • They are optimal with respect to connectivity and cycle embedding. [ABSTRACT FROM AUTHOR]

The strong geodetic number, sg (G) , of a graph G is the smallest number of vertices such that by fixing a suitable geodesic between each pair of selected vertices, all vertices of the graph are covered. In this paper, the formula for sg (K n , m) is given, as well as a formula for the crown graphs S n 0 . Bounds on the strong geodetic number of the hypercube Q n are also discussed. [ABSTRACT FROM AUTHOR]

System-level diagnosis has become an important diagnosis method for multiprocessor systems. Among all system-level diagnosis measures, diagnosability is relatively small. The conditional diagnosability constraint that each vertex has at least one good neighbor is relatively conservative when the dimension is far greater than 1, and g-good-neighbor conditional diagnosability does not consider this restriction on faulty vertices. Therefore, a thorough study of diagnosability under the condition that each vertex has at least g good neighbors is an appealing subject. Motivated by R g vertex connectivity, in this paper, we introduce a novel generalized system-level diagnosis measure named R g conditional diagnosability, which assumes that every processor has at least g good neighbors. The popular conditional diagnosability is a special case of R g conditional diagnosability when g = 1. Then, we determine that the R g conditional diagnosability of n -dimensional hypercube Q n under the Preparata Metze Chien (PMC) model is 2 2 g (n − 2 g) + 2 2 g − 1 − 1. [ABSTRACT FROM AUTHOR]

We propose two new measures of conditional connectivity to be the extension of Rg-connectivity and Rg-edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) degG–F(p) + degG–F(q) ≥ 2g + k for every two distinct vertices p and q in G – F with d(p, q) ≤ d. The (g, d, k)-conditional(-edge)-connectivity, denoted by κg,d,k(λg,d,k), is the minimum cardinality of a conditional (g, d, k)(-edge)-cut. Based on these requirements, we obtain κ1,1,k, κ1,d,2, λ1,1,1 and λ1,d,2 for the hypercubes. [ABSTRACT FROM AUTHOR]

Transmission of a vertex u in a graph G is defined as T(u) = ∑ v∈V(G) d(u,v) [1]. The expression T(G) = 1/2∑ u,v∈V(G) d(u,v) is called the transmission of G. Further the cardinality of the set {T(u)/u ∈ V(G)} is addressed as the transmission dimension of G and is denoted by dim T (G) [5]. Closeness centrality of a vertex v in G is defined as the reciprocal of the transmission of v. Using this centrality measure, the most important vertices in the graph are identified. In this paper we have computed the transmission of every vertex of an r -regular caterpillar and a spanning tree of the hypercube network. [ABSTRACT FROM AUTHOR]

We propose two new measures of conditional connectivity to be the extension of Rg-connectivity and Rg-edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) degG–F(p) + degG–F(q) ≥ 2g + k for every two distinct vertices p and q in G – F with d(p, q) ≤ d. The (g, d, k)-conditional(-edge)-connectivity, denoted by κg,d,k(λg,d,k), is the minimum cardinality of a conditional (g, d, k)(-edge)-cut. Based on these requirements, we obtain κ1,1,k, κ1,d,2, λ1,1,1 and λ1,d,2 for the hypercubes. [ABSTRACT FROM AUTHOR]

The surface of a 3-dimensional cube can be continuously flattened onto any of its faces, by moving creases to change the shapes of some faces successively, following Sabitov's volume preserving theorem. Let C n be an n-dimensional cube with n ≥ 4 , and S be the set of its 2-dimensional faces, i.e., the 2-dimensional skeleton of the square faces in C n . We show that S can be continuously flattened onto any face F of S, such that the faces of S that are parallel to F, do not have any crease, that is, they are rigid during the motion. [ABSTRACT FROM AUTHOR]

We study bond percolation on the hypercube {0,1}m in the slightly subcritical regime where p = pc(1 − εm) and εm = o(1) but εm ≫ 2−m/3 and study the clusters of largest volume and diameter. We establish that with high probability the largest component has cardinality Θεm−2log(εm32m), that the maximal diameter of all clusters is (1+o(1))εm−1log(εm32m), and that the maximal mixing time of all clusters is Θεm−3log2(εm32m). These results hold in different levels of generality, and in particular, some of the estimates hold for various classes of graphs such as high‐dimensional tori, expanders of high degree and girth, products of complete graphs, and infinite lattices in high dimensions. [ABSTRACT FROM AUTHOR]

A d -dimensional matrix is called 1 -polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1 -permutation matrix. A diagonal of a d -dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d -dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order n and dimension d , the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d , we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least n n 3 / 2 (1 / 2 − o (1)) 1-permutation matrices and contains a polytope of dimension at least c n 3 / 2 for fixed c , d and even n → ∞. We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent. For odd d , we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions. [ABSTRACT FROM AUTHOR]

We live in a three-dimensional (3D) spatial world; however, our retinas receive a pair of 2D projections of the 3D environment. By using multiple cues, such as disparity, motion parallax, perspective, our brains can construct 3D representations of the world from the 2D projections on our retinas. These 3D representations underlie our 3D perceptions of the world and are mapped into our motor systems to generate accurate sensorimotor behaviors. Three-dimensional perceptual and sensorimotor capabilities emerge during development: the physiology of the growing baby changes hence necessitating an ongoing re-adaptation of the mapping between 3D sensory representations and the motor coordinates. This adaptation continues in adulthood and is quite general to successfully deal with joint-space changes (longer arms due to growth), skull and eye size changes (and still being able of accurate eye movements), etc. A fundamental question is whether our brains are inherently limited to 3D representations of the environment because we are living in a 3D world, or alternatively, our brains may have the inherent capability and plasticity of representing arbitrary dimensions; however, 3D representations emerge from the fact that our development and learning take place in a 3D world. Here, we review research related to inherent capabilities and limitations of brain plasticity in terms of its spatial representations and discuss whether with appropriate training, humans can build perceptual and sensorimotor representations of spatial 4D environments, and how the presence or lack of ability of a solid and direct 4D representation can reveal underlying neural representations of space. [ABSTRACT FROM AUTHOR]

We consider the problem of existence of a Hamiltonian cycle containing a matching and avoiding some edges in an n-cube Qn; and obtain the following results. Let n ⩾ 3; M ⊂ E(Qn); and F ⊂ E(Qn)M with 1 ⩽ |F| ⩽ 2n − 4 − |M|: If M is a matching and every vertex is incident with at least two edges in the graph Qn − F; then all edges of M lie on a Hamiltonian cycle in Qn − F: Moreover, if |M| = 1 or |M| = 2; then the upper bound of number of faulty edges tolerated is sharp. Our results generalize the well-known result for |M| = 1 [ABSTRACT FROM AUTHOR]

We present a simple construction of an acute set of size 2 d - 1 + 1 in R d for any dimension d. That is, we explicitly give 2 d - 1 + 1 points in the d-dimensional Euclidean space with the property that any three points form an acute triangle. It is known that the maximal number of such points is less than 2 d . Our result significantly improves upon a recent construction, due to Dmitriy Zakharov, with size of order φ d where φ = (1 + 5) / 2 ≈ 1.618 is the golden ratio. [ABSTRACT FROM AUTHOR]

We compare two kinds of pursuit-evasion games played on graphs. In Cops and Robbers, the cops can move strategically to adjacent vertices as they please, while in a new variant, called deterministic Zombies and Survivors, the zombies (the counterpart of the cops) are required to always move towards the survivor (the counterpart of the robber). The cop number of a graph is the minimum number of cops required to catch the robber on that graph; the zombie number of a graph is the minimum number of zombies required to catch the survivor on that graph. We answer two questions from the 2016 paper of Fitzpatrick, Howell, Messinger, and Pike. We show that for any integers m and k such that m ≥ k ≥ 1 , there is a graph with zombie number m and cop number k. We also show that the zombie number of the n -dimensional hypercube is ⌈ 2 n ∕ 3 ⌉. [ABSTRACT FROM AUTHOR]

We consider the sum of the coordinates of a simple random walk on the K-dimensional hypercube and prove a double asymptotic of this process, as both the time parameter n and the space parameter K tend to infinity. Depending on the asymptotic ratio of the two parameters, the rescaled processes converge toward either a "stationary Brownian motion," an Ornstein–Uhlenbeck process or a Gaussian white noise. [ABSTRACT FROM AUTHOR]

• Consider Q n with | F e | + | F v | ≤ n − 3 faulty edges and vertices, where n ≥ 3. • There are vertex-disjoint odd paths P [ u , v ] and P [ x , y ] with lengths sum from 2 to 2 n − 2 | F v | − 2 in Q n joining edges (u , v) and (x , y). • One application is that we obtain Q n − F e is bipancyclic, where | F e | ≤ n − 2. • The result is optimal with respect to the number of fault-tolerant elements. Let Q n denote the n -dimensional hypercube and the set of faulty edges and faulty vertices in Q n be denoted by F e and F v , respectively. In this paper, we investigate Q n (n ≥ 3) with | F e | + | F v | ≤ n − 3 faulty elements, and demonstrate that there are two fault-free vertex-disjoint paths P [ a , b ] and P [ c , d ] satisfying that 2 ≤ ℓ (P [ a , b ]) + ℓ (P [ c , d ]) ≤ 2 n − 2 | F v | − 2 , where 2 | (ℓ (P [ a , b ]) + ℓ (P [ c , d ])) , (a , b) , (c , d) ∈ E (Q n). The contribution of this paper is: (1) we can quickly obtain the interesting result that Q n − F e is bipancyclic, where | F e | ≤ n − 2 and n ≥ 3 ; (2) this result is a complement to Chen's part result (Chen (2009) [2]) in that our result shows that there are all kinds of two disjoint-free (S , T) -paths which contain 4 , 6 , 8 , ... , 2 n − 2 | F v | vertices respectively in Q n when S = { a , c } , T = { b , d } , and (a , b) , (c , d) ∈ E (Q n). Our result is optimal with respect to the number of fault-tolerant elements. [ABSTRACT FROM AUTHOR]

Given a graph G, the exact distance-p graph G [ ♮ p ] has V(G) as its vertex set, and two vertices are adjacent whenever the distance between them in G equals p. We present formulas describing the structure of exact distance-p graphs of the Cartesian, the strong, and the lexicographic product. We prove such formulas for the exact distance-2 graphs of direct products of graphs. We also consider infinite grids and some other product structures. We characterize the products of graphs of which exact distance graphs are connected. The exact distance-p graphs of hypercubes Q n are also studied. As these graphs contain generalized Johnson graphs as induced subgraphs, we use some known constructions of their colorings. These constructions are applied for colorings of the exact distance-p graphs of hypercubes with the focus on the chromatic number of Q n [ ♮ p ] for p ∈ { n - 2 , n - 3 , n - 4 } . [ABSTRACT FROM AUTHOR]

A function f: f0; 1gn! f0; 1g is said to be k-monotone if it flips between 0 and 1 at most k times on every ascending chain. Such functions represent a natural generalization of (1-)monotone functions, and have been recently studied in circuit complexity, PAC learning, and cryptography. Our work is part of a renewed focus in understanding testability of properties characterized by freeness of arbitrary order patterns as a generalization of monotonicity. Recently, Canonne et al. [Innovations in Theoretical Computer Science, Schloss-Dagstuhl{Leibniz-Zentrum für Informatik GmBH, Wadern, Germany, 2017, 29] initiate the study of k-monotone functions in the area of property testing, and Newman et al. [SODA, SIAM, Philadelphia, 2017, pp. 1582{1597] study testability of families characterized by freeness from order patterns on real-valued functions over the line [n] domain. We study k-monotone functions in the more relaxed parametrized property testing model, introduced by Parnas, Ron, and Rubinfeld [J. Comput. System Sci., 72 (2006), pp. 1012{1042]. In this process we show strong lower bounds on testing k-monotonicity. Specifically, we show that testing 2-monotonicity on the hypercube nonadaptively with one-sided error requires an exponential in p n number of queries. This behavior shows a stark contrast with testing (1-)monotonicity, which only needs ~O -p n = queries. Furthermore, even the apparently easier task of distinguishing 2-monotone functions from functions that are far from being n:01-monotone also requires an exponential number of queries. [ABSTRACT FROM AUTHOR]