Some results on entire functions of finite lower order

Letf(z) be an entire function of order λ and of finite lower order μ. If the zeros off(z) accumulate in the vicinity of a finite number of rays, then

1. λ is finite;
2. for every arbitrary numberk ₁>1, there existsk ₂>1 such thatT(k ₁ r,f)≤k ₂ T(r,f) for allr≥r ₀. Applying the above results, we prove that iff(z) is extremal for Yang's inequalityp=g/2, then
3. every deficient values off(z) is also its asymptotic value;
4. every asymptotic value off(z) is also its deficient value;
5. λ=μ;
6. $\sum\limits_{a \ne \infty } {\delta (a,f) \leqslant 1 - k(\mu ).} $

     

Compactness and the axiom of choice

In the absence of the axiom of choice four versions of compactness (A-, B-, C-, and D-compactness) are investigated. Typical results:

1. C-compact spaces form the epireflective hull in Haus of A-compact completely regular spaces.
2. Equivalent are:
3. the axiom of choice,
4. A-compactness = D-compactness,
5. B-compactness = D-compactness,
6. C-compactness = D-compactness and complete regularity,
7. products of spaces with finite topologies are A-compact,
8. products of A-compact spaces are A-compact,
9. products of D-compact spaces are D-compact,
10. powers X ^k of 2-point discrete spaces are D-compact,
11. finite products of D-compact spaces are D-compact,
12. finite coproducts of D-compact spaces are D-compact,
13. D-compact Hausdorff spaces form an epireflective subcategory of Haus,
14. spaces with finite topologies are D-compact.

1. Equivalent are:
2. the Boolean prime ideal theorem,
3. A-compactness = B-compactness,
4. A-compactness and complete regularity = C-compactness,
5. products of spaces with finite underlying sets are A-compact,
6. products of A-compact Hausdorff spaces are A-compact,
7. powers X ^k of 2-point discrete spaces are A-compact,
8. A-compact Hausdorff spaces form an epireflective subcategory of Haus.

1. Equivalent are:
2. either the axiom of choice holds or every ultrafilter is fixed,
3. products of B-compact spaces are B-compact.

1. Equivalent are:
2. Dedekind-finite sets are finite,
3. every set carries some D-compact Hausdorff topology,
4. every T ₁-space has a T ₁-D-compactification,
5. Alexandroff-compactifications of discrete spaces and D-compact.

     

Packing seagulls

A seagull in a graph is an induced three-vertex path. When does a graph G have k pairwise vertex-disjoint seagulls? This is NP-complete in general, but for graphs with no stable set of size three we give a complete solution. This case is of special interest because of a connection with Hadwiger’s conjecture which was the motivation for this research; and we deduce a unification and strengthening of two theorems of Blasiak [2] concerned with Hadwiger’s conjecture. Our main result is that a graph G (different from the five-wheel) with no three-vertex stable set contains k disjoint seagulls if and only if

1. |V (G)|≥3k
2. G is k-connected
3. for every clique C of G, if D denotes the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C then |D|+|V (G)\C|≥2k, and
4. the complement graph of G has a matching with k edges.

We also address the analogous fractional and half-integral packing questions, and give a polynomial time algorithm to test whether there are k disjoint seagulls.     

Bounding the vertex cover number of a hypergraph

For a hypergraphH, we denote by

1. τ(H) the minimumk such that some set ofk vertices meets all the edges,
2. ν(H) the maximumk such that somek edges are pairwise disjoint, and
3. λ(H) the maximumk≥2 such that the incidence matrix ofH has as a submatrix the transpose of the incidence matrix of the complete graphK _k .

We show that τ(H) is bounded above by a function of ν(H) and λ(H), and indeed that if λ(H) is bounded by a constant then τ(H) is at most a polynomial function of ν(H).     

Parking structures: Fuss analogs

For any irreducible real reflection group W with Coxeter number h, Armstrong, Reiner, and the author introduced a pair of \(W \times {\mathbb {Z}}_{h}\) -modules which deserve to be called W-parking spaces which generalize the type A notion of parking functions and conjectured a relationship between them. In this paper we give a Fuss analog of their constructions. For a Fuss parameter k≥1, we define a pair of \(W \times {\mathbb {Z}}_{kh}\) -modules which deserve to be called k-W-parking spaces and conjecture a relationship between them. We prove the weakest version of our conjectures for each of the infinite families ABCDI of finite reflection groups, together with proofs of stronger versions in special cases. Whenever our weakest conjecture holds for W, we have the following corollaries.

• There is a simple formula for the character of either k-W-parking space.
• We recover a cyclic sieving result due to Krattenthaler and Müller which gives the cycle structure of a generalized rotation action on k-W-noncrossing partitions.
• When W is crystallographic, the restriction of either k-W-parking space to W is isomorphic to the action of W on the finite torus Q/(kh+1)Q, where Q is the root lattice.

     

On the completion of excellent rings in characteristicp>0

Si considera il seguente problema posto da Grothendieck (E.G.A.): SeA è un anello eccellente edm un ideale diA, (A, m) ^{^}=m-adico completamento diA è eccellente? Si mostra che la risposta è positiva nei seguenti casi:

1. A=algebra di tipo finito su un DVR completo di caratteristicap>0;
2. A=algebra di tipo finito su un DVRC contenente un corpok di caratteristicap>0 e finito suk [C ^p ] oppure tale che:

1. per ogni sottocampok′ dik contenentek ^p tale che [k:k′]<∞, il modulo universale finito dei differenzialiD _{k′ (C)} esiste;
2. il corpo residuoK diC soddisfa rank _KK ? _K/k <∞
3. C ha una Der-base.

     

On lines missing polyhedral sets in 3-space

We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:

1. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
2. AnO(n ^1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
3. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
4. An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n ^4/3+ε+k ^1/3 n ^1+ε+klog² n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].

The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space.     

States on bounded commutative residuated lattices

We define states on bounded commutative residuated lattices and consider their property. We show that, for a bounded commutative residuated lattice X,

1. If s is a state, then X/ker(s) is an MV-algebra.
2. If s is a state-morphism, then X/ker(s) is a linearly ordered locally finite MV-algebra.

Moreover we show that for a state s on X, the following statements are equivalent:

1. s is a state-morphism on X.
2. ker(s) is a maximal filter of X.
3. s is extremal on X.

     

Multidimensional symmetric stable processes

This paper surveys recent remarkable progress in the study of potential theory for symmetric stable processes. It also contains new results on the two-sided estimates for Green functions, Poisson kernels and Martin kernels of discontinuous symmetric α-stable process in boundedC ^1,1 open sets. The new results give explicit information on how the comparing constants depend on parameter α and consequently recover the Green function and Poisson kernel estimates for Brownian motion by passing α ↑ 2. In addition to these new estimates, this paper surveys recent progress in the study of notions of harmonicity, integral representation of harmonic functions, boundary Harnack inequality, conditional gauge and intrinsic ultracontractivity for symmetric stable processes. Here is a table of contents.

1. Introduction
2. Green function and Poisson kernel estimates

1. Estimates on balls
2. Estimates on boundedC ^1,1 domains
3. Estimates on boundedC ^1,1 open sets

1. Harmonic functions and integral representation
2. Two notions of harmonicity
3. Martin kernel and Martin boundary
4. Integral representation and uniqueness
5. Boundary Harnack principle
6. Conditional process and its limiting behavior
7. Conditional gauge and intrinsic ultracontractivity

     

Homogeneity in infinite permutation groups

It is shown that ifG is a permutation group on an infinite setX, andG is (k?1)-transitive but notk-transitive (wherek ≥ 5), then the following hold:

1. G is not (k + 3)-homogeneous.
2. IfG is (k + 2)-homogeneous, then the group induced byG on ak-subset ofX is the alternating groupA _k .

     

On linear and semidefinite programming relaxations for hypergraph matching

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following:

We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Füredi, Kahn and Seymour, showing that the integrality gap is exactly ${k-1+\frac{1}{k}}$ for k-uniform hypergraphs, and is exactly k ? 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems.

We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k ? 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most ${\frac{k+1}{2}}$ for k-uniform hypergraphs. The construction uses a result in extremal combinatorics.

We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovász ${\vartheta}$ -function provides an SDP relaxation with integrality gap at most ${\frac{k+1}{2}}$ . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming relaxations.

     

k-convexn-person games and their cores

For any natural numbersk andn, the subclass ofk-convexn-person games is introduced. In casek=n, the subclass consists of the convexn-person games. Ak-convexn-person game is characterized in several ways in terms of the core and certain marginal worth vectors. The marginal worth vectors of a game are described in terms of an upper bound for the core and the corresponding gap function. It is shown that thek-convexity of ann-person gamev is equivalent to

1. all marginal worth vectors ofv belong to the core ofv; or
2. the core ofv is the convex hull of the set consisting of all marginal worth vectors ofv; or
3. the extreme points of the core ofv are exactly the marginal worth vectors ofv.

Examples ofk-convexn-person games are also treated.     

Cyclic algebras,complete fields,and crossed products

Theorem 1

Let q=char(k). Let M be a subfield of D which is Galois over K of degree m with Galois group H.

1. If q/m then H has a normal q-Sylow subgroup.
2. Iq q ? m then H is an abelian group with one or two generators, an extension of a cyclic group by a cyclic group of order e where k contains a primitive e-th root of unity.

Letk(X) be the generic division ring overk of indexn as defined by Amitsur.

Theorem 2

If n is divisible by the square of a prime p≠char(k) and k does not contain a primitive p-th root of unity, then k(X) is not a crossed product.     

Ramanujan graphs

A large family of explicitk-regular Cayley graphsX is presented. These graphs satisfy a number of extremal combinatorial properties.

1. For eigenvaluesλ ofX eitherλ=±k or ¦λ¦≦2 √k?1. This property is optimal and leads to the best known explicit expander graphs.
2. The girth ofX is asymptotically ≧4/3 log _k?1 ¦X¦ which gives larger girth than was previously known by explicit or non-explicit constructions.

     

On the exactness of certain inequalities in approximation theory

We prove the following: for every sequence {F_v}, F_v ? 0, F_v > 0 there exists a functionf such that

1. E_n(f)?F_n (n=0, 1, 2, ...) and
2. A_kn^?k? _v=1 ⁿ v^k?1 F_v?1?Ω_k (f, n^?1) (n=1, 2, ...).

     

Slightly triangulated graphs are perfect

A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C _k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(\forall k \geqslant 5,C_{k,} \bar C_k \nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions;

1. G contains no chordless cycle with at least 5 vertices.
2. For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.

     

On the complexity of the herding attack and some related attacks on hash functions

In this article, we analyze the complexity of the construction of the 2 ^k -diamond structure proposed by Kelsey and Kohno (LNCS, Vol 4004, pp 183–200, 2006). We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the message complexity (i.e., the number of hash computations required to build the required structure). We also analyze the computational complexity for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following:

1. The message complexity for the construction of a diamond structure is ${\sqrt{k}}$ times more than the amount previously stated in literature.

1. The time complexity is n times the message complexity, where n is the size of hash value.

Due to the above two results, the herding attack (Kelsey and Kohno, LNCS, Vol 4004, pp 183–200, 2006) and the second preimage attack (Andreeva et?al., LNCS, Vol 4965, pp 270–288, 2008) on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on “hash twice” is n times the complexity claimed by Andreeva et?al. (LNCS, Vol 5867, pp 393–414, 2009), by giving a more detailed analysis of the attack.     

Fast perfect-information leader-election protocols with linear immunity

In this paper we develop a leader election protocolP with the following features:

1. The protocol rums in theperfect information model: Every step taken by a player is visible to all others.
2. It haslinear immunity: IfP is run byn players and a coalition ofc ₁ n players deviates from the protocol, attempting to have one of them elected, their probability of success is <1-c ₂, wherec ₁,c ₂>0 are absolute constants.
3. It isfast: The running time ofP is polylogarithmic inn, the number of players.

A previous protocol by Alon and Naor achieving linear immunity in the perfect information model has a linear time complexity. The main ingredient of our protocol is areduction subprotocol. This is a way forn players to elect a subset of themselves which has the following property. Assume that up toen of the players are bad and try to have as many of them elected to the subset. Then with high probability, the fraction of bad players among the elected ones will not exceede in a significant way. The existence of such a reduction protocol is first established by a probabilistic argument. Later an explicit construction is provided which is based on the spectral properties of Ramanujan graphs.     

Normalizers,Centralizers and Action Representability in Semi-Abelian Categories

We introduce the notion of normalizer as motivated by the classical notion in the category of groups. We show for a semi-abelian category ? that the following conditions are equivalent:

1. ? is action representable and normalizers exist in ?;
2. the category Mono(?) of monomorphisms in ? is action representable;
3. the category ?² of morphisms in ? is action representable;
4. for each category \(\mathbb {D}\) with a finite number of morphisms the category \({\mathbb {C}} ^{\mathbb {D}}\) is action representable.

Moreover, when in addition ? is locally well-presentable, we show that these conditions are further equivalent to:

1. ? satisfies the amalgamation property for protosplit normal monomorphism and ? satisfies the axiom of normality of unions;
2. for each small category \(\mathbb {D}\) , the category \({\mathbb {C}} ^{\mathbb {D}}\) is action representable.

We also show that if ? is homological, action accessible, and normalizers exist in ?, then ? is fiberwise algebraically cartesian closed.