Forbidden (0,1)-vectors in Hyperplanes of $$\mathbb{R}^{n}$$: The unrestricted case

In this paper, we continue our investigation on “Extremal problems under dimension constraints” introduced [1]. The general problem we deal with in this paper can be formulated as follows. Let be an affine plane of dimension k in . Given determine or estimate .Here we consider and solve the problem in the special case where is a hyperplane in and the “forbidden set” . The same problem is considered for the case, where is a hyperplane passing through the origin, which surprisingly turns out to be more difficult. For this case we have only partial results.AMS Classification: 05C35, 05B30, 52C99     

Testing balancedness and perfection of linear matrices

A (0, 1) matrix is linear if it does not contain a 2×2 submatrix of all ones. In this paper we give polynomial algorithms to test whether a linear matrix is balanced or perfect. The algorithms are based on decomposition results previously obtained by the authors.Partial support under NSF Grants DMS 8606188, DDM8800281 and DDM9001705.     

Exceptions and characterization results for type‐1 λ‐designs

Let $X$ be a finite set with $v$ elements, called points and $\beta$ be a family of subsets of $X$, called blocks. A pair $\left(X,\beta \right)$ is called $\lambda$‐design whenever $\mid \beta \mid =\mid X\mid$ and

• 1. for all $B_i,B_j\in \beta ,i\ne j,\mid B_i\cap B_j\mid =\lambda$;
• 2. for all $B_j\in \beta ,\mid B_j\mid =k_j>\lambda$, and not all $k_j$ are equal.

The only known examples of $\lambda$‐designs are so‐called type‐1 designs, which are obtained from symmetric designs by a certain complementation procedure. Ryser and Woodall had independently conjectured that all $\lambda$‐designs are type‐1. Let $r,r^{*}?(r>r^{*})$ be replication numbers of a $\lambda$‐design $D=\left(X,\beta \right)$ and $g=\text{gcd}\left(r?1,r^{*}?1\right),m=\text{gcd}\left(\left(r?r^{*}\right)∕g,\lambda \right)$, and $m\prime =m$, if $m$ is odd and $m\prime =m∕2$, otherwise. For distinct points $x$ and $y$ of $D$, let $\lambda \left(x,y\right)$ denote the number of blocks of $X$ containing $x$ and $y$. We strengthen a lemma of S.S. Shrikhande and N.M. Singhi and use it to prove that if $\frac{r\left(r?1\right)}{\left(v?1\right)}?\frac{k\left(r?r^{*}\right)}{m\prime \left(v?1\right)}$ are not integers for $k=1,2,\text{…},m\prime ?1$, then $D$ is type‐1. As an application of these results, we show that for fixed positive integer $\theta$ there are finitely many nontype‐1 $\lambda$‐designs with $r=r^{*}+\theta$. If $r?r^{*}=27$ or $r?r^{*}=4p$ and $r^{*}\ne {\left(p?1\right)}^2$, or $v=7p+1$ such that $p?1,13\left(\mathrm{mod}21\right)$ and $p?4,9,19,24\left(\mathrm{mod}35\right)$, where $p$ is a positive prime, then $D$ is type‐1. We further obtain several inequalities involving $\lambda (x,y)$, where equality holds if and only if D is type‐1.     

Some results on λ‐designs with two block sizes

A λ‐design is a family ?? = {B₁, B₂, …, B_v} of subsets of X = {1, 2, …, v} such that |B_i∩B_j| = λ for all i≠jand not all B_i are of the same size. The only known example of λ‐designs (called type‐1 designs) are those obtained from symmetric designs by a certain complementation procedure. Ryser [J Algebra 10 (1968), 246–261] and Woodall [Proc London Math Soc 20 (1970), 669–687] independently conjectured that all λ‐designs are type‐1. Let g = gcd(r ? 1, r^* ? 1), where rand r^* are the two replication numbers. Ionin and Shrikhande [J Combin Comput 22 (1996), 135–142; J Combin Theory Ser A 74 (1996), 100–114] showed that λ‐designs with g = 1, 2, 3, 4 are type‐1 and that the Ryser–Woodall conjecture is true for λ‐designs on p + 1, 2p + 1, 3p + 1, 4p + 1 points, where pis a prime. Hein and Ionin [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 145–156] proved corresponding results for g = 5 and Fiala [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 109–124; Ars Combin 68 (2003), 17–32; Ars Combin, to appear] for g = 6, 7, and 8. In this article, we consider λ designs with exactly two block sizes. We show that in this case, the conjecture is true for g = 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, and for g = 10, 14, 18, 22 with v≠4λ ? 1. We also give two results on such λ‐designs on v = 9p + 1 and 12p + 1 points, where pis a prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:95‐110, 2011     

On the existence of resolvable K4 − e designs

In this article, we settle a problem which originated in 4 regarding the existence of resolvable (K₄ ? e)‐design. We solve the problem with two possible exceptions. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 502–510, 2007     

Large set of P3‐decompositions

Let G=(V(G),E(G)) be a graph. A (n,G, λ)‐GD is a partition of the edges of λK_n into subgraphs (G‐blocks), each of which is isomorphic to G. The (n,G,λ)‐GD is named as graph design for G or G‐decomposition. The large set of (n,G,λ)‐GD is denoted by (n,G,λ)‐LGD. In this work, we obtain the existence spectrum of (n,P₃,λ)‐LGD. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 151–159, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10008     

Ideal polytopes and face structures of some combinatorial optimization problems

Given a finite setX and a family of feasible subsetsF ofX, the 0–1 polytope P (F is defined as the convex hull of all the characteristic vectors of members ofF We show that under a certain assumption a special type of face ofP(F) is equivalent to the ideal polytope of some pseudo-ordered set. Examples of families satisfying the assumption are those related to the maximum stable set problem, set packing and set partitioning problems, and vertex coloring problem. Using this fact, we propose a new heuristic for such problems and give results of our preliminary computational experiments for the maximum stable set problem.Supported by a JSPS Fellowship for Young Scientists.Supported by Grant-in-Aids for Co-operative Research (06740147) of the Ministry of Education, Science and Culture.     

Co-NP-completeness of some matrix classification problems

The classes of P-, P ₀-, R ₀-, semimonotone, strictly semimonotone, column sufficient, and nondegenerate matrices play important roles in studying solution properties of equations and complementarity problems and convergence/complexity analysis of methods for solving these problems. It is known that the problem of deciding whether a square matrix with integer/rational entries is a P- (or nondegenerate) matrix is co-NP-complete. We show, through a unified analysis, that analogous decision problems for the other matrix classes are also co-NP-complete. Received: April 1999 / Accepted: March 1, 2000?Published online May 12, 2000     

A construction of resolvable nested 3‐designs

A method of constructing resolvable nested 3‐designs from an affine resolvable 3‐design is proposed with one example. © 2004 Wiley Periodicals, Inc.     

Categorical Abstract Algebraic Logic: Algebraic Semantics for (\documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\bf{\pi }$\end{document})‐Institutions

Various aspects of the work of Blok and Rebagliato on the algebraic semantics for deductive systems are studied in the context of logics formalized as π‐institutions. Three kinds of semantics are surveyed: institution, matrix (system) and algebraic (system) semantics, corresponding, respectively, to the generalized matrix, matrix and algebraic semantics of the theory of sentential logics. After some connections between matrix and algebraic semantics are revealed, it is shown that every (finitary) N‐rule based extension of an N‐rule based π‐institution possessing an algebraic semantics also possesses an algebraic semantics. This result abstracts one of the main theorems of Blok and Rebagliato. An attempt at a Blok‐Rebagliato‐style characterization of those π‐institutions with a mono‐unary category of natural transformations on their sentence functors having an algebraic semantics is also made. Finally, a necessary condition for a π‐institution to possess an algebraic semantics is provided.     

On extensions of some Flugede–Putnam type theorems involving (p,k)‐quasihyponormal,spectral, and dominant operators

A Hilbert space operator S is called (p, k)‐quasihyponormal if S *^k ((S *S)^p – (SS *)^p )S^k ≥ 0 for an integer k ≥ 1 and 0 < p ≤ 1. In the present note, we consider (p, k)‐quasihyponormal operator S ∈ B (H) such that SX = XT for some X ∈ B (K,H) and prove the Fuglede–Putnam type theorems when the adjoint of T ∈ B (K) is either (p, k)‐quasihyponormal or dominant or a spectral operator (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Higher‐order generalized invexity in variational problems

We introduce higher‐order duality (Mangasarian type and Mond–Wier type) of variational problems. Under higher‐order generalized invexity assumptions on functions that compose the primal problem, higher‐order duality results (weak duality, strong duality, and converse duality) are derived for this pair of problems. Also, we establish many examples and counter‐examples to support our investigation. Copyright © 2012 John Wiley & Sons, Ltd.     

Some applications of a cardinality estimate for a certain configuration

Two configurations are constructed and the cardinality of one of them is estimated in terms of that of the other. The estimate thus obtained is applied to certain combinatorial problems. Translated fromMatematicheskie Zametki, Vol. 63, No. 5, pp. 729–736, May, 1998.     

On (∈, ∈ ∨ q)‐fuzzy filters of R0‐algebras

In this paper, we introduce the notions of (∈, ∈ ∨ q)‐fuzzy filters and (∈, ∈ ∨ q)‐fuzzy Boolean (implicative) filters in R₀‐algebras and investigate some of their related properties. Some characterization theorems of these generalized fuzzy filters are derived. In particular, we prove that a fuzzy set in R₀‐algebras is an (∈, ∈ ∨ q)‐fuzzy Boolean filter if and only if it is an (∈, ∈ ∨ q)‐fuzzy implicative filter. Finally, we consider the concepts of implication‐based fuzzy Boolean (implicative) filters of R₀‐algebras (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

(p,q)‐Generalization of Szász–Mirakyan operators

In this paper, we introduce new modifications of Szász–Mirakyan operators based on (p,q)‐integers. We first give a recurrence relation for the moments of new operators and present explicit formula for the moments and central moments up to order 4. Some approximation properties of new operators are explored: the uniform convergence over bounded and unbounded intervals is established, direct approximation properties of the operators in terms of the moduli of smoothness is obtained and Voronovskaya theorem is presented. For the particular case p = 1, the previous results for q‐Sz ász–Mirakyan operators are captured. Copyright © 2015 John Wiley & Sons, Ltd.     

Exact solutions of nonlinear Schrödinger equation by using symbolic computation

The (G′/G,1/G)‐expansion method and (1/G′)‐expansion method are interesting approaches to find new and more general exact solutions to the nonlinear evolution equations. In this paper, these methods are applied to construct new exact travelling wave solutions of nonlinear Schrödinger equation. The travelling wave solutions are expressed by hyperbolic functions, trigonometric functions and rational functions. It is shown that the proposed methods provide a powerful mathematical tool for solving nonlinear wave equations in mathematical physics and engineering. Copyright © 2015 John Wiley & Sons, Ltd.     

Positive Frege and its Scott‐style semantics

We show that the untyped λ ‐calculus can be extended with Frege's interpretation of propositional notions, provided we restrict β ‐conversion to positive expressions. The system of illative λ ‐calculus so obtained admits a natural Scott‐style semantics. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The existence of a 2‐factor in K1, n‐free graphs with large connectivity and large edge‐connectivity

In this article, we study the existence of a 2‐factor in a K_{1, n}‐free graph. Sumner [J London Math Soc 13 (1976), 351–359] proved that for n?4, an (n?1)‐connected K_{1, n}‐free graph of even order has a 1‐factor. On the other hand, for every pair of integers m and n with m?n?4, there exist infinitely many (n?2)‐connected K_{1, n}‐free graphs of even order and minimum degree at least m which have no 1‐factor. This implies that the connectivity condition of Sumner's result is sharp, and we cannot guarantee the existence of a 1‐factor by imposing a large minimum degree. On the other hand, Ota and Tokuda [J Graph Theory 22 (1996), 59–64] proved that for n?3, every K_{1, n}‐free graph of minimum degree at least 2n?2 has a 2‐factor, regardless of its connectivity. They also gave examples showing that their minimum degree condition is sharp. But all of them have bridges. These suggest that the effects of connectivity, edge‐connectivity and minimum degree to the existence of a 2‐factor in a K_{1, n}‐free graph are more complicated than those to the existence of a 1‐factor. In this article, we clarify these effects by giving sharp minimum degree conditions for a K_{1, n}‐free graph with a given connectivity or edge‐connectivity to have a 2‐factor. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 68:77‐89, 2011     

The spectrum of BSA(v, 3, λ; α) with α = 2,3

In this article, a kind of auxiliary design BSA^* for constructing BSAs is introduced and studied. Two powerful recursive constructions on BSAs from 3‐IGDDs and BSA^*s are exploited. Finally, the necessary and sufficient conditions for the existence of a BSA(v, 3, λ; α) with α = 2, 3 are established. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 61–76, 2007