A branching scheme for minimum cost tournaments with regard to real-world constraints

Single round robin tournaments are a well-known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated with each possible match. Moreover, stadium availability, fixed matches, and regions’ capacities are taken into account. The goal is to find the minimum cost tournament among those having the minimum number of breaks and being feasible with regard to these additional constraints. A branching scheme is developed where branching is done by fixing a break for a team. Thus, the focus is on identifying breaks leading to an infeasible home away pattern set in order to avoid the resulting infeasible subtrees of a branch and bound tree.     

On a new property of <Emphasis Type="Italic">n</Emphasis>-poised and <Emphasis Type="Italic">G</Emphasis><Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> sets

In this paper we consider n-poised planar node sets, as well as more special ones, called G C _n sets. For the latter sets each n-fundamental polynomial is a product of n linear factors as it always holds in the univariate case. A line ? is called k-node line for a node set \(\mathcal X\) if it passes through exactly k nodes. An (n + 1)-node line is called maximal line. In 1982 M. Gasca and J. I. Maeztu conjectured that every G C _n set possesses necessarily a maximal line. Till now the conjecture is confirmed to be true for n ≤ 5. It is well-known that any maximal line M of \(\mathcal X\) is used by each node in \(\mathcal X\setminus M, \)meaning that it is a factor of the fundamental polynomial. In this paper we prove, in particular, that if the Gasca-Maeztu conjecture is true then any n-node line of G C _n set \(\mathcal {X}\) is used either by exactly \(\binom {n}{2}\) nodes or by exactly \(\binom {n-1}{2}\) nodes. We prove also similar statements concerning n-node or (n ? 1)-node lines in more general n-poised sets. This is a new phenomenon in n-poised and G C _n sets. At the end we present a conjecture concerning any k-node line.     

Density of solutions to quadratic congruences

A classical result in number theory is Dirichlet’s theorem on the density of primes in an arithmetic progression. We prove a similar result for numbers with exactly k prime factors for k > 1. Building upon a proof by E.M. Wright in 1954, we compute the natural density of such numbers where each prime satisfies a congruence condition. As an application, we obtain the density of squarefree n ≤ x with k prime factors such that a fixed quadratic equation has exactly 2 ^k solutions modulo n.     

A realization theorem in the context of the Schur-Szegő composition

Every real polynomial of degree n in one variable with root ?1 can be represented as the Schur-Szeg? composition of n ? 1 polynomials of the form (x + 1) ^n?1(x + a _i ), where the numbers a _i are uniquely determined up to permutation. Some a _i are real, and the others form complex conjugate pairs. In this note, we show that for each pair (ρ, r), where 0 ? ρ, r ? [n/2], there exists a polynomial with exactly ρ pairs of complex conjugate roots and exactly r complex conjugate pairs in the corresponding set of numbers a _i .     

On the Strong <Emphasis Type="Italic">n</Emphasis>-partite Tournaments with Exactly Two Cycles of Length <Emphasis Type="Italic">n</Emphasis> − 1

Gutin and Rafiey (Australas J. Combin. 34 (2006), 17-21) provided an example of an n-partite tournament with exactly n ? m + 1 cycles of length of m for any given m with 4 ≤ m ≤ n, and posed the following question. Let 3 ≤ m ≤ n and n ≥ 4. Are there strong n-partite tournaments, which are not themselves tournaments, with exactly n ? m + 1 cycles of length m for two values of m? In the same paper, they showed that this question has a negative answer for two values n ? 1 and n. In this paper, we prove that a strong n-partite tournament with exactly two cycles of length n ? 1 must contain some given multipartite tournament as subdigraph. As a corollary, we also show that the above question has a negative answer for two values n ? 1 and any l with 3 ≤ l ≤ n and l ≠ n ? 1.     

On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets

Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.     

NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations

Three series of number-theoretic problems with explicitly defined parameters concerning systems of Diophantine dis-equations with solutions from a given domain are considered. Constraints on these parameters under which any problem of each series is NP-complete are proved. It is proved that for any m and m′ (m < m′) the consistency problem on the segment [m, m′] for a system of linear Diophantine dis-equations, each of which contains exactly three variables (even if the coefficients at these variables belong to {–1, 1}), is NP-complete. This problem admits a simple geometric interpretation of NP-completeness for the determination of whether there exists an integer-valued point inside a multidimensional cube that is not covered by given hyperplanes that cut off equal segments on three arbitrary axes and are parallel to all other axes. If in a system of linear Diophantine dis-equations each dis-equation contains exactly two variables, the problem remains NP-complete under the condition that the following inequality holds: m′–m > 2. It is also proved that if the solution to a system of linear Diophantine dis-equations, each containing exactly three variables, is sought in the domain given by a system of polynomial inequalities that contain an n-dimensional cube and are contained in an n-dimensional parallelepiped symmetric with respect to the point of origin, its consistency problem is NP-complete.     

Difference Covering Arrays and Pseudo-Orthogonal Latin Squares

A pair of Latin squares, A and B, of order n, is said to be pseudo-orthogonal if each symbol in A is paired with every symbol in B precisely once, except for one symbol with which it is paired twice and one symbol with which it is not paired at all. A set of t Latin squares, of order n, are said to be mutually pseudo-orthogonal if they are pairwise pseudo-orthogonal. A special class of pseudo-orthogonal Latin squares are the mutually nearly orthogonal Latin squares (MNOLS) first discussed in 2002, with general constructions given in 2007. In this paper we develop row complete MNOLS from difference covering arrays. We will use this connection to settle the spectrum question for sets of 3 mutually pseudo-orthogonal Latin squares of even order, for all but the order 146.     

Independence numbers of random subgraphs of a distance graph

We consider the so-called distance graph G(n, 3, 1), whose vertices can be identified with three-element subsets of the set {1, 2,..., n}, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of G(n, 3, 1) in the Erd?s–Rényi model, in which each edge is included in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, 3, 1).     

On distance Gray codes

A Gray code of size n is a cyclic sequence of all binary words of length n such that two consecutive words differ exactly in one position. We say that the Gray code is a distance code if the Hamming distance between words located at distance k from each other is equal to d. The distance property generalizes the familiar concepts of a locally balanced Gray code. We prove that there are no distance Gray codes with d = 1 for k > 1. Some examples of constructing distance Gray codes are given. For one infinite series of parameters, it is proved that there are no distance Gray codes.     

Complexity of function systems over a finite field in the class of polarized polynomial forms

The Shannon complexity of a function system over a q-element finite field which contains m functions of n variables in the class of polarized polynomial forms is exactly evaluated: L _q ^PPF (n,m) = q ⁿ for all n ≥ 1, m ≥ 2, and all possible odd q. It has previously been known that L₂^PPF (n,m) = 2 ⁿ and L₃^PPF (n,m) = 3 ⁿ for all n ≥ 1 and m ≥ 2.     

An Ore-Type Theorem on Hamiltonian Square Cycles

The kth power of a cycle C is the graph obtained from C by joining every pair of vertices with distance at most k on C. The second power of a cycle is called a square cycle. Pósa conjectured that every graph with minimum degree at least 2n/3 contains a hamiltonian square cycle. Later, Seymour proposed a more general conjecture that if G is a graph with minimum degree at least (kn)/(k + 1), then G contains the kth power of a hamiltonian cycle. Here we prove an Ore-type version of Pósa’s conjecture that if G is a graph in which deg(u) + deg(v) ≥ 4n/3 ? 1/3 for all non-adjacent vertices u and v, then for sufficiently large n, G contains a hamiltonian square cycle unless its minimum degree is exactly n/3 + 2 or n/3 + 5/3. A consequence of this result is an Ore-type analogue of a theorem of Aigner and Brandt.     

Automorphisms of Coxeter groups of type <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

A Coxeter system (W, S) is said to be of type K _n if the associated Coxeter graph Γ_S is complete on n vertices and has only odd edge labels. If W satisfies either of: (1) n = 3; (2) W is rigid; then the automorphism group of W is generated by the inner automorphisms of W and any automorphisms induced by Γ_S. Indeed, Aut(W) is the semidirect product of Inn(W) and the group of diagram automorphisms, and furthermore W is strongly rigid. We also show that if W is a Coxeter group of type K _n then W has exactly one conjugacy class of involutions and hence Aut(W) = Spec(W).     

Coherence relative to a weak torsion class

Let R be a ring. A subclass T of left R-modules is called a weak torsion class if it is closed under homomorphic images and extensions. Let T be a weak torsion class of left R-modules and n a positive integer. Then a left R-module M is called T-finitely generated if there exists a finitely generated submodule N such that M/N ∈ T; a left R-module A is called (T,n)-presented if there exists an exact sequence of left R-modules

$$0 \to {K_{n - 1}} \to {F_{n - 1}} \to \cdots \to {F_1} \to {F_0} \to M \to 0$$

such that F₀,..., F_n?1 are finitely generated free and K_n?1 is T-finitely generated; a left R-module M is called (T,n)-injective, if Ext ⁿ _R (A,M) = 0 for each (T, n+1)-presented left R-module A; a right R-module M is called (T,n)-flat, if Tor ^R _n (M,A) = 0 for each (T, n+1)-presented left R-module A. A ring R is called (T,n)-coherent, if every (T, n+1)-presented module is (n + 1)-presented. Some characterizations and properties of these modules and rings are given.

     

Facets of the <Emphasis Type="Italic">r</Emphasis>-Stable (<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-Hypersimplex

Let k, n, and r be positive integers with k < n and \({r \leq \lfloor \frac{n}{k} \rfloor}\). We determine the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the r-stable n, k-hypersimplex has exactly 2n facets for every \({r < \lfloor \frac{n}{k} \rfloor}\). We then utilize the equations of the facets to study when the r-stable hypersimplex is Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices known to have unimodal Ehrhart \({\delta}\)-vectors.     

Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions

In this paper, we improve existing results in the field of compressed sensing and matrix completion when sampled data may be grossly corrupted. We introduce three new theorems. (1) In compressed sensing, we show that if the m×n sensing matrix has independent Gaussian entries, then one can recover a sparse signal x exactly by tractable ? ₁ minimization even if a positive fraction of the measurements are arbitrarily corrupted, provided the number of nonzero entries in x is O(m/(log(n/m)+1)). (2) In the very general sensing model introduced in Candès and Plan (IEEE Trans. Inf. Theory 57(11):7235–7254, 2011) and assuming a positive fraction of corrupted measurements, exact recovery still holds if the signal now has O(m/(log² n)) nonzero entries. (3) Finally, we prove that one can recover an n×n low-rank matrix from m corrupted sampled entries by tractable optimization provided the rank is on the order of O(m/(nlog² n)); again, this holds when there is a positive fraction of corrupted samples.     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

Characterization of 2-Local Derivations and Local Lie Derivations on Some Algebras

We prove that each 2-local derivation from the algebra M_n(A ) (n > 2) into its bimodule M_n(M) is a derivation, where A is a unital Banach algebra and M is a unital A -bimodule such that each Jordan derivation from A into M is an inner derivation, and that each 2-local derivation on a C*-algebra with a faithful traceable representation is a derivation. We also characterize local and 2-local Lie derivations on some algebras such as von Neumann algebras, nest algebras, the Jiang–Su algebra, and UHF algebras.     

Fair 1-Factorizations and Fair Holey 1-Factorizations of Complete Multipartite Graphs

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If \(V_{1},\ldots , V_{p}\) are the p parts of V(K(n, p)), then a holey k -factor of deficiency \(V_{i}\) of K(n, p) is a k-factor of \(K(n,p)-V_{i}\) for some i satisfying \(1\le i \le p\). Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared “evenly” among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each \(n \times n\) “box”. These quasigroups are in some sense as far from frames produced by direct products as possible.     

Note edge-colourings of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n,n</Emphasis></Subscript> with no long two-coloured cycles

Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K _n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K _n,n with n colours having all two-coloured cycles of length ≤ 2q ², for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K _n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4.