Search

A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper, we show that if K is a maximum resonant set of P, then P - K has a unique perfect matching. We further prove that the maximum forcing number of a polyomino graph is equal to the cardinality of a maximum resonant set. This confirms a conjecture of Xu et al. [26]. We also show that if K is a maximal alternating set of P, then P - K has a unique perfect matching. [ABSTRACT FROM AUTHOR]

Let K = { k 1 , k 2 , … , k r } and L = { l 1 , l 2 , … , l s } be disjoint subsets of { 0 , 1 , ⋯ p − 1 } , where p is a prime and F = { F 1 , F 2 , … , F m } be a family of subsets of [ n ] such that | F i | (mod p ) ∈ K for all F i ∈ F and | F i ∩ F j | (mod p ) ∈ L for i ≠ j . In 1991 Alon, Babai and Suzuki conjectured that if n ≥ s + max 1 ≤ i ≤ r k i , then | F | ≤ n s + n s − 1 + ⋯ + n s − r + 1 . In this paper we prove this conjecture. [ABSTRACT FROM AUTHOR]

Abstract: In Huang et al. [17] it was proved that for any Nil d Bohr0-set , there are a minimal system and a non-empty open subset of with , and for any minimal system and any open non-empty , the set is an almost Nil d Bohr0-set. The polynomial form of this problem is considered in this paper. It is shown that the latter is still true in the polynomial case, while the former is not in general. We also consider the special case when the system is a nilsystem. [Copyright &y& Elsevier]

Abstract: In this paper, three classes of monomials and one class of trinomials over finite fields of even characteristic are proposed. They are proved to be complete permutation polynomials. [Copyright &y& Elsevier]

Abstract: The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an time and polynomial space algorithm. [Copyright &y& Elsevier]

Abstract: Let G be a classical group and suppose that G does not contains non-trivial graph automorphisms. In this paper we prove that the order complex of the coset poset of G is non-contractible. In order to prove it, we show that does not vanish, where is the Dirichlet polynomial associated to the group G. [Copyright &y& Elsevier]

We propose two admissible closures $${\mathbb{A}({\sf PTCA})}$$ and $${\mathbb{A}({\sf PHCA})}$$ of Ferreira's system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) $${\mathbb{A}({\sf PTCA})}$$ is conservative over PTCA with respect to $${\forall\exists\Sigma^b_1}$$ sentences, and (ii) $${\mathbb{A}({\sf PHCA})}$$ is conservative over full bounded arithmetic PHCA for $${\forall\exists\Sigma^b_{\infty}}$$ sentences. This yields that (i) the $${\Sigma^b_1}$$ definable functions of $${\mathbb{A}({\sf PTCA})}$$ are the polytime functions, and (ii) the $${\Sigma^b_{\infty}}$$ definable functions of $${\mathbb{A}({\sf PHCA})}$$ are the functions in the polynomial time hierarchy. [ABSTRACT FROM AUTHOR]

Abstract.  The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multi-prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from one by an inverse-polynomial in the input size, and one extra prover. Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This “public-coin” property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single-prover ones. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the uniform norm on $[0, 1]$ over non-zero polynomials $p$ of the form$$p(x) = \sum_{j=0}^n a_jx^j \quad\text{with } |a_j| \le 1,\, a_j \in {\Bbb C},$$where the modulus of the first non-zero coefficient is at least $\delta > 0$. Essentially sharp bounds are given for this problem. An interesting related result states that there are absolute constants $c_1 > 0$ and $c_2 > 0$ such that$$ \exp (-c_1 \sqrt{n} ) \le \inf_{0 \ne p \in {\cal F}_n }\|p\|_{[0, 1]} \le \exp (-c_2 \sqrt{n}),$$for every $n \ge 2$, where ${\cal F}_n$ denotes the set of polynomials of degree at most $n$ with coefficients from $\{-1, 0, 1 \}$. This Chebyshev-type problem is closely related to the question of how many zeros a polynomial from the above classes can have at $1$. We also give essentially sharp bounds for this problem.{\em Inter alia} we prove that there is an absolute constant $c > 0$ such that every polynomial $p$ of the form$$p(x) = \sum_{j=0}^n a_j x^j, \quad\text{with } |a_j| \le 1,\,|a_0|=|a_n|=1,\, a_j \in {\Bbb C},$$has at most $c\sqrt{n}$ real zeros. This improves the old bound $c\sqrt{n\log n}$ given by Schur in 1933, as well as more recent related bounds of Bombieri and Vaaler, and, up to the constant $c$, this is the best possible result.All the analysis rests critically on the key estimate stating that there are absolute constants $c_1 > 0$ and $c_2 > 0$ such that$$|f(0)|^{c_1/a} \le \exp (c_2/a)\|f\|_{[1-a,1]},$$for every $f \in {\cal S}$ and $a \in (0, 1]$, where $\cal S$ denotes the collection of all analytic functions $f$ on the open unit disk $D := \{ z \in {\Bbb C}: |z| < 1 \}$ that satisfy$$|f(z)| \le \frac{1}{1-|z|}\quad \text{for } z \in D.$$ [ABSTRACT FROM AUTHOR]

The article offers information on sparse complete set in nondeterministic polynomial time (NP) and coNP. It mentions that two corallaries on the relationships between the reductibility notions were obtained from a comparison of theorems. Moreover, it states that the proof of theorem four follows Mahaney's proof of Theorem 2 wherein his idea was to introduce a pseudo complement.