Search results for "rete"

Forests and pattern-avoiding permutations modulo pure descents

2018

Abstract We investigate an equivalence relation on permutations based on the pure descent statistic. Generating functions are given for the number of equivalence classes for the set of all permutations, and the sets of permutations avoiding exactly one pattern of length three. As a byproduct, we exhibit a permutation set in one-to-one correspondence with forests of ordered binary trees, which provides a new combinatorial class enumerated by the single-source directed animals on the square lattice. Furthermore, bivariate generating functions for these sets are given according to various statistics.

Über den Rang der projektiven Darstellung von Kettengeometrien auf Grassmann-Mannigfaltigkeiten

1985

An optimal bound for embedding linear spaces into projective planes

1988

Abstract Linear spaces with υ >n 2 − 1 2 n + 1 points, b⩽n2 + n + 1 lines and not constant point degree are classified. It turns out that there is essentially one class of such linear spaces which are not near pencils and which can not be embedded into any projective plane of order n.

Cyclic and lift closures for k…21-avoiding permutations

2011

We prove that the cyclic closure of the permutation class avoiding the pattern k(k-1)...21 is finitely based. The minimal length of a minimal permutation is 2k-1 and these basis permutations are enumerated by (2k-1).c"k where c"k is the kth Catalan number. We also define lift operations and give similar results. Finally, we consider the toric closure of a class and we propose some open problems.

Tighter Relations between Sensitivity and Other Complexity Measures

2014

The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].

Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory

2007

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponenti…

Extremum degree sets of irregular oriented graphs and pseudodigraphs

2006

Spaces of typen on partially ordered sets

1989

This paper contains a generalized approach to incidence geometry on partially ordered sets. A difference to the usual geometrical concepts is that points may have different size. Our main result states that a large class of spaces allows lattice theoretic characterizations. Especially, a generalized version of the Veblen-Young axiom of projective geometry has a lattice theoretic equivalent, called then-generation property (which is a generalization of the ‘Verbindungssatz’). Modularity and distributivity of a lattice of subspaces are reflected in the underlying space. Finally we give specializations and examples.

Correspondences Between 2-Brauer Characters of Solvable Groups

2010

Let G be a finite solvable group and let p be a prime. Let P ∈ Syl p (G) and N = N G (P). We prove that there exists a natural bijection between the 2-Brauer irreducible characters of p′-degree of G and those of N G (P).

On a Linear Diophantine Problem of Frobenius: Extending the Basis

1998

LetXk={a1, a2, …, ak},k>1, be a subset of N such that gcd(Xk)=1. We shall say that a natural numbernisdependent(onXk) if there are nonnegative integersxisuch thatnhas a representationn=∑ki=1 xiai, elseindependent. The Frobenius numberg(Xk) ofXkis the greatest integer withnosuch representation. Selmer has raised the problem of extendingXkwithout changing the value ofg. He showed that under certain conditions it is possible to add an elementc=a+kdto the arithmetic sequencea,a+d,a+2d, …, a+(k−1) d, gcd(a, d)=1, without alteringg. In this paper, we give the setCof all independent numberscsatisfyingg(A, c)=g(A), whereAcontains the elements of the arithmetic sequence. Moreover, ifa>kthen we give …