The Hausdorff dimension of a class of recurrent sets

In this paper we obtain a lower bound for the Hausdorff dimension of recurrent sets and, in a general setting, we show that a conjecture of Dekking [F.M. Dekking, Recurrent sets: A fractal formalism, Report 82-32, Technische Hogeschool, Delft, 1982] holds.     

A counterexample to the triangle conjecture

The triangle conjecture sets a bound on the cardinality of a code formed by words of the form aⁱba^j. A counterexample exceeding that bound is given. This also disproves a stronger conjecture that every code is commutatively equivalent to a prefix code.     

Distance Measures for Well-Distributed Sets

In this paper we investigate the Erdos/Falconer distance conjecture for a natural class of sets statistically, though not necessarily arithmetically, similar to a lattice. We prove a good upper bound for spherical means that have been classically used to study this problem. We conjecture that a majorant for the spherical means suffices to prove the distance conjecture(s) in this setting. For a class of non-Euclidean distances, we show that this generally cannot be achieved, at least in dimension two, by considering integer point distributions on convex curves and surfaces. In higher dimensions, we link this problem to the question about the existence of smooth well-curved hypersurfaces that support many integer points.     

Derivatives of Faber Polynomials and Markov Inequalities

We study asymptotic behavior of the derivatives of Faber polynomials on a set with corners at the boundary. Our results have applications to the questions of sharpness of Markov inequalities for such sets. In particular, the found asymptotics are related to a general Markov-type inequality of Pommerenke and the associated conjecture of Erd s. We also prove a new bound for Faber polynomials on piecewise smooth domains.     

Maximal sets with no solution to <Emphasis Type="Italic">x</Emphasis>+<Emphasis Type="Italic">y</Emphasis>=3<Emphasis Type="Italic">z</Emphasis>

In this paper, we are interested in a generalization of the notion of sum-free sets. We address a conjecture rst made in the 90s by Chung and Goldwasser. Recently, after some computer checks, this conjecture was formulated again by Matolcsi and Ruzsa, who made a rst signicant step towards it. Here, we prove the full conjecture by giving an optimal upper bound for the Lebesgue measure of a 3-sum-free subset A of [0; 1], that is, a set containing no solution to the equation x+y=3z where x, y and z are restricted to belong to A. We then address the inverse problem and characterize precisely, among all sets with that property, those attaining the maximal possible measure.     

Computation of differential Chow forms for ordinary prime differential ideals

In this paper, we propose algorithms for computing differential Chow forms for ordinary prime differential ideals which are given by characteristic sets. The algorithms are based on an optimal bound for the order of a prime differential ideal in terms of a characteristic set under an arbitrary ranking, which shows the Jacobi bound conjecture holds in this case. Apart from the order bound, we also give a degree bound for the differential Chow form. In addition, for a prime differential ideal given by a characteristic set under an orderly ranking, a much simpler algorithm is given to compute its differential Chow form. The computational complexity of the algorithms is single exponential in terms of the Jacobi number, the maximal degree of the differential polynomials in a characteristic set, and the number of variables.     

A New Approach to Extracting Roots in Garside Groups

We study the problem of extracting roots in Garside groups by reducing it to the calculation of certain ultra summit sets. Several properties concerning the roots and an effective algorithm are derived. In particular, in the case of braid groups, a conjecture on the bound of super summit set implies that, for fixed number of strands and ordinal number of root, the algorithm is polynomial in the word length.     

The graph formulation of the union-closed sets conjecture

The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs. We derive that the union-closed sets conjecture holds for all union-closed families being the union-closure of sets of size at most three.     

Fixed‐parameter decidability: Extending parameterized complexity analysis

We extend the reach of fixed‐parameter analysis by introducing classes of parameterized sets defined based on decidability instead of complexity. Known results in computability theory can be expressed in the language of fixed‐parameter analysis, making use of the landscape of these new classes. On the one hand this unifies results that would not otherwise show their kinship, while on the other it allows for further exchange of insights between complexity theory and computability theory. In the landscape of our fixed‐parameter decidability classes, we recover part of the classification of real numbers according to their computability. From this, using the structural properties of the landscape, we get a new proof of the existence of P ‐selective bi‐immune sets. Furthermore, we show that parameter values in parameterized sets in our uniformly fixed‐parameter decidability classes interact with both instance complexity and Kolmogorov complexity. By deriving a parameter based upper bound on instance complexity, we demonstrate how parameters convey a sense of randomness. Motivated by the instance complexity conjecture, we show that the upper bound on the instance complexity is infinitely often also an upper bound on the Kolmogorov complexity.     

Lower bound theorem for normal pseudomanifolds

In this paper we present a self-contained combinatorial proof of the lower bound theorem for normal pseudomanifolds, including a treatment of the cases of equality in this theorem. We also discuss McMullen and Walkup's generalized lower bound conjecture for triangulated spheres in the context of the lower bound theorem. Finally, we pose a new lower bound conjecture for non-simply connected triangulated manifolds.     

The union-closed sets conjecture almost holds for almost all random bipartite graphs

Frankl’s union-closed sets conjecture states that in every finite union-closed family of sets, not all empty, there is an element in the ground set contained in at least half of the sets. The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets.We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl’s conjecture.     

A family of skew Hadamard difference sets

In 1933 a family of skew Hadamard difference sets was described by Paley using matrix language and was called the Paley-Hadamard difference sets in the literature. During the last 70 years, no new skew Hadamard difference sets were found. It was conjectured that there are no further examples of skew Hadamard difference sets. This conjecture was proved to be true for the cyclic case in 1954, and further progress in favor of this conjecture was made in the past 50 years. However, the conjecture remains open until today. In this paper, we present a family of new perfect nonlinear (also called planar) functions, and construct a family of skew Hadamard difference sets using these perfect nonlinear functions. We show that some of the skew Hadamard difference sets presented in this paper are inequivalent to the Paley-Hadamard difference sets. These new examples of skew Hadamard difference sets discovered 70 years after the Paley construction disprove the longstanding conjecture on skew Hadamard difference sets. The class of new perfect nonlinear functions has applications in cryptography, coding theory, and combinatorics.     

Divisibility properties of values of partial zeta functions at non-positive integers

We conjecture a new bound on the exact denominators of the values at non-positive integers of imprimitive partial zeta functions associated with an Abelian extension of number fields. At s?=?0, this conjecture is closely connected to a conjecture of David Hayes. We prove the new conjecture assuming that the Coates–Sinnott conjecture holds for the extension.     

The Field Descent Method

We obtain a broadly applicable decomposition of group ring elements into a “subfield part” and a “kernel part”. Applications include the verification of Lander’s conjecture for all difference sets whose order is a power of a prime >3 and for all McFarland, Spence and Chen/Davis/Jedwab difference sets. We obtain a new general exponent bound for difference sets. We show that there is no circulant Hadamard matrix of order v with 4<v<548, 964, 900 and no Barker sequence of length l with 13 < l ≤ 10²².     

Maximum union-free subfamilies

An old problem of Moser asks: what is the size of the largest union-free subfamily that one can guarantee in every family of m sets? A family of sets is called union-free if there are no three distinct sets in the family such that the union of two of the sets is equal to the third set. We show that every family of m sets contains a union-free subfamily of size at least \(\left\lfloor {\sqrt {4m + 1} } \right\rfloor - 1\) and that this bound is tight. This solves Moser’s problem and proves a conjecture of Erd?s and Shelah from 1972.More generally, a family of sets is a-union-free if there are no a + 1 distinct sets in the family such that one of them is equal to the union of a others. We determine up to an absolute multiplicative constant factor the size of the largest guaranteed a-union-free subfamily of a family of m sets. Our result verifies in a strong form a conjecture of Barat, Füredi, Kantor, Kim and Patkos.     

Newton polygons and curve gonalities

We give a combinatorial upper bound for the gonality of a curve that is defined by a bivariate Laurent polynomial with given Newton polygon. We conjecture that this bound is generically attained, and provide proofs in a considerable number of special cases. One proof technique uses recent work of M. Baker on linear systems on graphs, by means of which we reduce our conjecture to a purely combinatorial statement.     

On the topological lower bound for the multichromatic number

In 1976, Stahl [14] defined the m-tuple coloring of a graph G and formulated a conjecture on the multichromatic number of Kneser graphs. For m=1 this conjecture is Kneser’s conjecture, which was proved by Lovász in 1978 [10]. Here we show that Lovász’s topological lower bound given in this way cannot be used to prove Stahl’s conjecture. We obtain that the strongest index bound only gives the trivial m⋅ω(G) lower bound if m≥|V(G)|. On the other hand, the connectivity bound for Kneser graphs is constant if m is sufficiently large. These findings provide new examples of graphs showing that the gaps between the chromatic number, the index bound and the connectivity bound can be arbitrarily large.     

强色指数的一个新的上界

给出了图的强色指数的一个新的上界，并指出几类恰好达到该上界的图，从而改进了Erodoes和Nesetri的强色指数猜想，在某种意义上证明了这个猜想。     

Equivalence of the strengthened Hanna Neumann conjecture and the amalgamated graph conjecture

Summary We show that Walter Neumann's strengthened form of Hanna Neumann's conjecture on the best possible upper bound for the rank of the intersection of two subgroups of a free group is equivalent to a conjecture on the best possible upper bound for the number of edges in a bipartite graph with a certain weak symmetry condition. We illustrate the usefulness of this equivalence by deriving relatively easily certain previously known results.Oblatum 30-VIII-1993     

Proof of grünbaum's conjecture on common transversals for translates

In 1958 B. Grünbaum made a conjecture concerning families of disjoint translates of a compact convex set in the plane: if such a family consists of at least five sets, and if any five of these sets are met by a common line, then some line meets all sets of the family. This paper gives a proof of the conjecture.