Coboundaries, Flows, and Tutte Polynomials of Matrices

Using matroid duality and the critical problem, we show that certain evaluations of the Tutte polynomial of a matroid represented as a matrix over a finite field GF(q) can be interpreted as weighted sums over pairs f , g of functions defined from the ground set to GF(q) whose difference f – g is the restriction of a linear functional on the column space of the matrix. Similar interpretations are given for the characteristic polynomial evaluated at q. These interpretations extend and elaborate interpretations for Tutte and chromatic polynomials of graphs due to Goodall and Matiyasevich. Received July 14, 2006     

Collapsing monoids consisting of permutations and constants

In this paper we determine all collapsing transformation monoids that contain at least one unary constant operation and whose nonconstant operations are permutations. Furthermore, we find an infinite family of transformation monoids that consist of at least three unary constant operations and some permutations for which the corresponding monoidal intervals are 2-element chains. This research is supported by Hungarian National Foundation for Scientific Research grant nos. T 37877 and K 60148.     

Some remarks on trigonometric sums

Let

Estimates for Mixed Character Sums

We give sharp estimates for certain families of exponential sums in several variables over finite fields. Received: May 2007, Accepted: September 2007     

Multilinear Exponential Sums in Prime Fields Under Optimal Entropy Condition on the Sources

The main result of this paper is an exponential sum bound in prime fields for multilinear expressions of the type under nearly optimal conditions on . It provides the expected generalization of the well-known inequality for r = 2. We also establish a new result on Gauss sums for multiplicative subgroups H of , obtaining a nontrivial estimate provided . This is a further improvement on [BGK]. Received: May 2007, Revision: October 2007, Accepted: October 2007     

Polytopes passing through circles

Suppose a convex body wants to pass through a circular hole in a wall. Does its ability to do so depend on the thickness of the wall? In fact in most cases it does, and in this paper we present a sufficient criterion for a polytope to allow an affirmative answer to the question.     

The operad of finite labeled tournaments

We study the operad of finite labeled tournaments. We describe the structure of suboperads of this operad generated by simple tournaments. We prove that a suboperad generated by a tournament with two vertices (i.e., the operad of finite linearly ordered sets) is isomorphic to the operad of symmetric groups, and a suboperad generated by a simple tournament with more that two vertices is isomorphic to the quotient operad of the free operad with respect to a certain congruence. We obtain this congruence explicitly.     

Reconstruction of Function Fields

For k an algebraic closure of the finite field , ℓ prime distinct from p and X a surface over k, we prove that the field of rational functions k(X) can be recovered from the maximal pro-ℓ-quotient of its absolute Galois group – in fact already from the second central descending series quotient of . Submitted: July 2004, Revision: October 2005, Final revision: February 2008, Accepted: February 2008     

Lectures on topology of words

We discuss a topological approach to words introduced by the author in [Tu2]–[Tu4]. Words on an arbitrary alphabet are approximated by Gauss words and then studied up to natural modifications inspired by the Reidemeister moves on knot diagrams. This leads us to a notion of homotopy for words. We introduce several homotopy invariants of words and give a homotopy classification of words of length five. Based on notes by Eri Hatakenaka, Daniel Moskovich, and Tadayuki Watanabe     

An application of index forms in cryptography

We investigate the possibility of using index forms as basic ingredients of cryptographically important functions. We suggest the use of a hash function based on index forms and we prove some important properties of the suggested function. The research was supported in part by the Hungarian Academy of Sciences, by grants T048791 and K67580 of the Hungarian NFSR, by the National Office for Research and Technology and by the grant JP-26/2006.     

Generalized bisymmetry on a restricted domain

Let X ⊂ ℝ be an interval of positive length and define the set Δ = {(x, y) ∈ X × X | x ≧ y}. We give the solution of the equation

A note on holomorphic approximation in Banach spaces

Given a complex Banach space X and a holomorphic function f on its unit ball B, we discuss the problem whether f can be approximated, uniformly on smaller balls, by functions g holomorphic on all of X. Research partially supported by NSF grant DMS0700281.     

Length Bounds on Curves Arising from Tight Geodesics

Let M be a complete hyperbolic 3-manifold admitting a homotopy equivalence to a compact surface ∑, such that the cusps of M are in bijective correspondence with the boundary components of ∑. Suppose we realise a tight geodesic in the curve complex as a sequence of closed geodesics M. There is an upper bound on the lengths of such curves in terms of the lengths of the terminal curves and the topologicial type of ∑. We give proofs of these and related bounds. Similar bounds have been proven by Minsky using the sophisticated machinery of hierarchies. Such bounds feature in the work of Brock, Canary and Minsky towards the ending lamination conjecture, and can also be used to study the action of the mapping class group on the curve complex. Received: January 2006, Revision: March 2007, Accepted: July 2007     

On the maximum number of points at least one unit away from each other in the unit <Emphasis Type="Italic">n</Emphasis>-cube

We present a very short survey of known results and many new estimates and results on the maximum number of points that can be chosen in the n-dimensional unit cube so that every distance between them is at least 1. Research was supported by Slovak national grant VEGA 1/3839/06.     

A Sidon basis

We construct a Sidon set which is an asymptotic additive basis of order at most 7.      

On the stability of the quadratic functional equation on bounded domains

A result of Skof and Terracini will be generalized; More precisely, we will prove that if a functionf : [-t, t]ⁿ →E satisfies the inequality (1) for some δ > 0 and for allx, y ∈ [-t, t]ⁿ withx + y, x - y ∈ [-t, t]ⁿ, then there exists a quadratic functionq: ℝⁿ →E such that ∥f(x) -q(x)∥ < (2912n² + 1872n + 334)δ for anyx ∈ [-t, t] ⁿ .     

On edge-antipodal <Emphasis Type="Italic">d</Emphasis>-polytopes

A convex d-polytope in ℝ ^d is called edge-antipodal if any two vertices that determine an edge of the polytope lie on distinct parallel supporting hyperplanes of the polytope. We introduce a program for investigating such polytopes, and examine those that are simple.      

Concatenation of pseudorandom binary sequences

In the applications it may occur that our initial pseudorandom binary sequence turns out to be not long enough, thus we have to take the concatenation or merging of it with other pseudorandom binary sequences. Here our goal is study when we can form the concatenation of several pseudorandom binary sequences belonging to a given family? We introduce and study new measures which can be used for answering this question.     

Solution of fifth-degree equations

In this paper we establish a relationship between two approaches to the solution of algebraic fifth-degree equations, namely, the Hermite-Kronecker method (based on the modular elliptic equation) and the Mellin method (based on hypergeometric series).