A local normal form theorem for infinitary logic with unary quantifiers

We prove a local normal form theorem of the Gaifman type for the infinitary logic L_∞ω( Q _u)^ω whose formulas involve arbitrary unary quantifiers but finite quantifier rank. We use a local Ehrenfeucht‐Fraïssé type game similar to the one in [9]. A consequence is that every sentence of L_∞ω( Q _u)^ω of quantifier rank n is equivalent to an infinite Boolean combination of sentences of the form (?^≥iy)ψ(y), where ψ(y) has counting quantifiers restricted to the (2^n–1 – 1)‐neighborhood of y. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fragments of Arithmetic and true sentences

By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the Π_n+1‐sentences true in the standard model is the only (up to deductive equivalence) consistent Π_n+1‐theory which extends the scheme of induction for parameter free Π_n+1‐formulas. Motivated by this result, we present a systematic study of extensions of bounded quantifier complexity of fragments of first‐order Peano Arithmetic. Here, we improve that result and show that this property describes a general phenomenon valid for parameter free schemes. As a consequence, we obtain results on the quantifier complexity, (non)finite axiomatizability and relative strength of schemes for Δ_n+1‐formulas. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On binary linear <Emphasis Type="Italic">r</Emphasis>-identifying codes

A subspace C of the binary Hamming space F ⁿ of length n is called a linear r-identifying code if for all vectors of F ⁿ the intersections of C and closed r-radius neighbourhoods are nonempty and different. In this paper, we give lower bounds for such linear codes. For radius r =  2, we give some general constructions. We give many (optimal) constructions which were found by a computer search. New constructions improve some previously known upper bounds for r-identifying codes in the case where linearity is not assumed.     

One‐factorizations of complete graphs with vertex‐regular automorphism groups

We consider one‐factorizations of K_2n possessing an automorphism group acting regularly (sharply transitively) on vertices. We present some upper bounds on the number of one‐factors which are fixed by the group; further information is obtained when equality holds in these bounds. The case where the group is dihedral is studied in some detail, with some non‐existence statements in case the number of fixed one‐factors is as large as possible. Constructions both for dihedral groups and for some classes of abelian groups are given. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 1–16, 2002     

Feedback Vertex Sets in Tournaments

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740ⁿ minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448ⁿ minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.     

The lower bounds of life span of classical solutions to one‐dimensional initial‐Neumann boundary value problems for general quasilinear wave equations

In this paper, we will study the lower bounds of the life span (the maximal existence time) of solutions to the initial‐boundary value problems with small initial data and zero Neumann boundary data on exterior domain for one‐dimensional general quasilinear wave equations u_tt?u_xx=b(u,Du)u_xx+F(u,Du). Our lower bounds of the life span of solutions in the general case and special case are shorter than that of the initial‐Dirichlet boundary value problem for one‐dimensional general quasilinear wave equations. We clarify that although the lower bounds in this paper are same as that in the case of Robin boundary conditions obtained in the earlier paper, however, the results in this paper are not the trivial generalization of that in the case of Robin boundary conditions because the fundamental Lemmas 2.4, 2.5, 2.6, and 2.7, that is, the priori estimates of solutions to initial‐boundary value problems with Neumann boundary conditions, are established differently, and then the specific estimates in this paper are different from that in the case of Robin boundary conditions. Another motivation for the author to write this paper is to show that the well‐posedness of problem 1.1 is the essential precondition of studying the lower bounds of life span of classical solutions to initial‐boundary value problems for general quasilinear wave equations. The lower bound estimates of life span of classical solutions to initial‐boundary value problems is consistent with the actual physical meaning. Finally, we obtain the sharpness on the lower bound of the life span 1.8 in the general case and 1.10 in the special case. Copyright © 2015 John Wiley & Sons, Ltd.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

Optimally small sumsets in groups IV. Counting multiplicities and the <Emphasis Type="Italic">λ</Emphasis><Subscript><Emphasis Type="Italic">G</Emphasis></Subscript> functions

We continue our investigation on how small a sumset can be in a given abelian group. Here small takes into account not only the size of the sumset itself but also the number of elements which are repeated at least twice. A function λ _G (r, s) computing the minimal size (in this sense) of the sum of two sets with respective cardinalities r and s is introduced. (Lower and upper) bounds are obtained, which coincide in most cases. While upper bounds are obtained by constructions, lower bounds follow in particular from the use of a recent theorem by Grynkiewicz.     

Vertex pancyclic in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. The topic of this paper is to investigate vertex k‐pancyclicity of in‐tournaments of order n, where for some 3 ≤ k ≤ n, every vertex belongs to a cycle of length p for every k ≤ p ≤ n. We give sharp lower bounds for the minimum degree such that a strong in‐tournament is vertex k‐pancyclic for k ≤ 5 and k ≥ n − 3. In the latter case, we even show that the in‐tournaments in consideration are fully (n − 3)‐extendable which means that every vertex belongs to a cycle of length n − 3 and that the vertex set of every cycle of length at least n − 3 is contained in a cycle of length one greater. In accordance with these results, we state the conjecture that every strong in‐tournament of order n with minimum degree greater than is vertex k‐pancyclic for 5 < k < n − 3, and we present a family of examples showing that this bound would be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 84–104, 2001     

Constructing Ramsey graphs from Boolean function representations

Explicit construction of Ramsey graphs or graphs with no large clique or independent set, has remained a challenging open problem for a long time. While Erdös’ probabilistic argument shows the existence of graphs on 2n vertices with no clique or independent set of size 2 ⁿ , the best explicit constructions achieve a far weaker bound. There is a connection between Ramsey graph constructions and polynomial representations of Boolean functions due to Grolmusz; a low degree representation for the OR function can be used to explicitly construct Ramsey graphs [17,18]. We generalize the above relation by proposing a new framework. We propose a new definition of OR representations: a pair of polynomials represent the OR function if the union of their zero sets contains all points in {0, 1} ⁿ except the origin. We give a simple construction of a Ramsey graph using such polynomials. Furthermore, we show that all the known algebraic constructions, ones to due to Frankl-Wilson [12], Grolmusz [18] and Alon [2] are captured by this framework; they can all be derived from various OR representations of degree O(√n) based on symmetric polynomials. Thus the barrier to better Ramsey constructions through such algebraic methods appears to be the construction of lower degree representations. Using new algebraic techniques, we show that better bounds cannot be obtained using symmetric polynomials.     

First and second moments for self‐similar couplings and Wasserstein distances

We study aspects of the Wasserstein distance in the context of self‐similar measures. Computing this distance between two measures involves minimising certain moment integrals over the space of couplings, which are measures on the product space with the original measures as prescribed marginals. We focus our attention on self‐similar measures associated to equicontractive iterated function systems consisting of two maps on the unit interval and satisfying the open set condition. We are particularly interested in understanding the restricted family of self‐similar couplings and our main achievement is the explicit computation of the 1st and 2nd moment integrals for such couplings. We show that this family is enough to yield an explicit formula for the 1st Wasserstein distance and provide non‐trivial upper and lower bounds for the 2nd Wasserstein distance for these self‐similar measures.     

Solvability criterion and representation of solutions of <Emphasis Type="Italic">n</Emphasis>-normal and <Emphasis Type="Italic">d</Emphasis>-normal linear operator equations in a Banach space

On the basis of a generalization of the well-known Schmidt lemma to the case of n-normal and d-normal linear bounded operators in a Banach space, we propose constructions of generalized inverse operators. We obtain criteria for the solvability of linear equations with these operators and formulas for the representation of solutions of these equations.     

Some Results on LΔ

We study the quantifier complexity and the relative strength of some fragments of arithmetic axiomatized by induction and minimization schemes for Δ_n+1 formulas.     

Edge‐decompositions of Kn,n into isomorphic copies of a given tree

We construct an incidence structure using certain points and lines in finite projective spaces. The structural properties of the associated bipartite incidence graphs are analyzed. These n × n bipartite graphs provide constructions of C₆‐free graphs with Ω(n^4/3 edges, C₁₀‐free graphs with Ω(n^6/5) edges, and Θ(7,7,7)‐free graphs with Ω(n^8/7) edges. Each of these bounds is sharp in order of magnitude. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 1–10, 2005     

The number of k‐SAT functions

We study the number SAT(k; n) of Boolean functions of n variables that can be expressed by a k‐SAT formula. Equivalently, we study the number of subsets of the n‐cube 2ⁿ that can be represented as the union of (n ? k)‐subcubes. In The number of 2‐SAT functions (Isr J Math, 133 (2003), 45–60) the authors and Imre Leader studied SAT(k; n) for k ≤ n/2, with emphasis on the case k = 2. Here, we prove bounds on SAT(k; n) for k ≥ n/2; we see a variety of different types of behavior. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 227–247, 2003     

Class‐uniformly resolvable designs

We investigate Class‐Uniformly Resolvable Designs, which are resolvable designs in which each of the resolution classes has the same number of blocks of each size. We derive the fully general necessary conditions including a number of extremal bounds. We present two general constructions. We primarily consider the case of block sizes 2 and 3, where we find two infinite extremal families and finish two other infinite families by difference constructions. We present tables showing the current state of knowledge in the case of block size 2 and 3 for all orders up to 200. © 2001 John Wiley & Sons, Inc. J Combin Designs 8: 79–99, 2001     

Constructing regular self‐complementary uniform hypergraphs

In this article, we examine the possible orders of t‐subset‐regular self‐complementary k‐uniform hypergraphs, which form examples of large sets of two isomorphic t‐designs. We reformulate Khosrovshahi and Tayfeh–Rezaie's necessary conditions on the order of these structures in terms of the binary representation of the rank k, and these conditions simplify to a more transparent relation between the order n and rank k in the case where k is a sum of consecutive powers of 2. Moreover, we present new constructions for 1‐subset‐regular self‐complementary uniform hypergraphs, and prove that these necessary conditions are sufficient for all k, in the case where t = 1. © 2011 Wiley Periodicals, Inc. J Combin Designs 19: 439‐454, 2011     

Size ramsey numbers of stars versus 4‐chromatic graphs

We investigate the asymptotics of the size Ramsey number î(K_1,nF), where K_1,n is the n‐star and F is a fixed graph. The author 11 has recently proved that r?(K_1,n,F)=(1+o(1))n² for any F with chromatic number χ(F)=3. Here we show that r?(K_1,n,F)≤ n²+o(n²), if χ (F) ≥ 4 and conjecture that this is sharp. We prove the case χ(F)=4 of the conjecture, that is, that r?(K_1,n,F)=(4+o(1))n² for any 4‐chromatic graph F. Also, some general lower bounds are obtained. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 220–233, 2003