Source author record

Béla Bajnok

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT math.CO math.MG math.PR

Catalog footprint

Research overview

10works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On two questions about restricted sumsets in finite abelian groups

Let $G$ be an abelian group of finite order $n$ , and let $h$ be a positive integer. A subset $A$ of $G$ is called {\em weakly $h$ -incomplete}, if not every element of $G$ can be written as the sum of $h$ distinct elements of $A$ ; in particular, if $A$ does not contain $h$ distinct elements that add to zero, then $A$ is called {\em weakly $h$ -zero-sum-free}. We investigate the maximum size of weakly $h$ -incomplete and weakly $h$ -zero-sum-free sets in $G$ , denoted by $C_h(G)$ and $Z_h(G)$ , respectively. Among our results are the following: (i) If $G$ is of odd order and $(n-1)/2 \leq h \leq n-2$ , then $C_h(G)=Z_h(G)=h+1$ , unless $G$ is an elementary abelian 3-group and $h=n-3$ ; (ii) If $G$ is an elementary abelian 2-group and $n/2 \leq h \leq n-2$ , then $C_h(G)=Z_h(G)=h+2$ , unless $h=n-4$ .

preprint2015arXiv

A Constructive Finite Field Method for Scattering Points on the Surface of $d$ -Dimensional Spheres

In this exploratory article, we present a constructive method for scattering points on the surface of $d$ dimensional spheres which we believe is new and of interest. Indeed, the problem of uniformly distributing points on spheres is an interesting and difficult problem with vast applications in fields as diverse as crystallography, approximation theory, computational complexity, molecular structure, and electrostatics.

preprint2015arXiv

Comments on Y. O. Hamidoune's Paper "Adding Distinct Congruence Classes"

The main result in Y.~O.~Hamidoune's paper "Adding Distinct Congruence Classes" ({\em Combin.~Probab.~Comput.}~{\bf 7} (1998) 81-87) is as follows: If $S$ is a generating subset of a cyclic group $G$ such that $0 \not \in S$ and $|S| \geq 5$ , then the number of sums of the subsets of $S$ is at least $\min (|G|, 2|S| )$ . Unfortunately, argument of the author, who, sadly, passed away in 2011, relies on a lemma whose proof is incorrect; in fact, the lemma is false for all cyclic groups of even order. In this short note we point out this mistake, correct the proof, and discuss why the main result is actually true for all finite abelian groups.

preprint2015arXiv

On Euclidean $t$ -designs

A Euclidean $t$ -design, as introduced by Neumaier and Seidel (1988), is a finite set ${\cal X} \subset \mathbb{R}^n$ with a weight function $w: {\cal X} \rightarrow \mathbb{R}^+$ for which $\sum_{r \in R} W_r \overline{f}_{S_{r}} = \sum_{{\bf x} \in {\cal X}} w({\bf x}) f({\bf x})$ holds for every polynomial $f$ of total degree at most $t$ ; here $R$ is the set of norms of the points in ${\cal X}$ , $W_r$ is the total weight of all elements of ${\cal X}$ with norm $r$ , $S_r$ is the $n$ -dimensional sphere of radius $r$ centered at the origin, and $\overline{f}_{S_{r}}$ is the average of $f$ over $S_{r}$ . Neumaier and Seidel (1988), as well as Delsarte and Seidel (1989), also proved a Fisher-type inequality $|{\cal X}| \geq N(n,|R|,t)$ (assuming that the design is antipodal if $t$ is odd). For fixed $n$ and $|R|$ we have $N(n,|R|,t)=O(t^{n-1})$ . In Part I of this paper we provide a recursive construction for Euclidean $t$ -designs in $\mathbb{R}^n$ . Namely, we show how to use certain Gauss--Jacobi quadrature formulae to "lift" a Euclidean $t$ -design in $\mathbb{R}^{n-1}$ to a Euclidean $t$ -design in $\mathbb{R}^{n}$ , preserving both the norm spectrum $R$ and the weight sum $W_r$ for each $r \in R$ . A Euclidean design with exactly $N(n,|R|,t)$ points is called tight. In Part II of this paper we construct tight Euclidean designs for $n=2$ and every $t$ and $|R|$ with $|R| \leq \frac{t+5}{4}$ . We also provide examples for tight Euclidean designs with $(n,|R|,t) \in \{(3,2,5),(3,3,7),(4,2,7)\}$ .

preprint2015arXiv

On the Minimum Width of a Cutset in the Truncated Boolean Lattice

For integers $0 \leq m \leq l \leq n-m$ , the truncated Boolean lattice ${\cal B}_n(m,l)$ is the poset of all subsets of $[n] = \{1, 2, \ldots, n\}$ which have size at least $m$ and at most $l$ . ${\cal C} \subseteq {\cal B}_n(m,l)$ is a {\em cutset} if it meets every chain of length $l-m$ in ${\cal B}_n(m,l)$ , and the {\em width} of ${\cal C}$ is the size of the largest antichain in ${\cal C}$ . We conjecture that for $n >> m$ the minimum width $h_n(m,l)$ of a cutset in ${\cal B}_n(m,l)$ is $Σ_{j \geq 0} Δ_n(m-jc) = Δ_n(m)+Δ_n(m-c)+Δ_n(m-2c)+ \dots$ , where $c=l-m+1$ is the number of level sets in ${\cal B}_n(m,l)$ and $Δ_n(k)={n \choose k}- {n \choose k-1}$ . We establish our conjecture for the cases of "short lattices" ( $l=m$ , $l=m+1$ , and $l=m+2$ ). For "taller lattices" ( $l \geq 2m$ ) our conjecture gives ${n \choose m} - {n \choose m-1}$ , independently of $l$ . Our main result is that $h_n(m,l) \leq {n \choose m} - {n \choose m-1}$ if $l \geq 2m$ .

preprint2015arXiv

On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice

Let $[n] = \{1, 2, \ldots, n\}$ and let $2^{[n]}$ be the collection of all subsets of $[n]$ ordered by inclusion. ${\cal C} \subseteq 2^{[n]}$ is a {\em cutset} if it meets every maximal chain in $2^{[n]}$ , and the {\em width} of ${\cal C} \subseteq 2^{[n]}$ is the minimum number of chains in a chain decomposition of ${\cal C}$ . Fix $0 \leq m \leq l \leq n$ . What is the smallest value of $k$ such that there exists a cutset that consists only of subsets of sizes between $m$ and $l$ , and such that it contains exactly $k$ subsets of size $i$ for each $m \leq i \leq l$ ? The answer, which we denote by $g_n(m,l)$ , gives a lower estimate for the width of a cutset between levels $m$ and $l$ in $2^{[n]}$ . After using the Kruskal-Katona Theorem to give a general characterization of cutsets in terms of the number and sizes of their elements, we find lower and upper bounds (as well as some exact values) for $g_n(m,l)$ .

preprint2015arXiv

Spherical Designs and Generalized Sum-Free Sets in Abelian Groups

We extend the concepts of sum-free sets and Sidon-sets of combinatorial number theory with the aim to provide explicit constructions for spherical designs. We call a subset $S$ of the (additive) abelian group $G$ {\it $t$ -free} if for all non-negative integers $k$ and $l$ with $k+l \leq t$ , the sum of $k$ (not necessarily distinct) elements of $S$ does not equal the sum of $l$ (not necessarily distinct) elements of $S$ unless $k=l$ and the two sums contain the same terms. Here we shall give asymptotic bounds for the size of a largest $t$ -free set in ${\bf Z}_n$ , and for $t \leq 3$ discuss how $t$ -free sets in ${\bf Z}_n$ can be used to construct spherical $t$ -designs.

preprint2015arXiv

The "Thirty-seven Percent Rule" and the Secretary Problem with Relative Ranks

We revisit the problem of selecting an item from $n$ choices that appear before us in random sequential order so as to minimize the expected rank of the item selected. In particular, we examine the stopping rule where we reject the first $k$ items and then select the first subsequent item that ranks lower than the $l$ -th lowest-ranked item among the first $k$ . We prove that the optimal rule has $k \sim n/{\mathrm e}$ , as in the classical secretary problem where our sole objective is to select the item of lowest rank; however, with the optimally chosen $l$ , here we can get the expected rank of the item selected to be less than any positive power of $n$ (as $n$ approaches infinity). We also introduce a common generalization where our goal is to minimize the expected rank of the item selected, but this rank must be within the lowest $d$ .

preprint2015arXiv

The independence number of a subset of an abelian group

We call a subset $A$ of the (additive) abelian group $G$ {\it $t$ -independent} if for all non-negative integers $h$ and $k$ with $h+k \leq t$ , the sum of $h$ (not necessarily distinct) elements of $A$ does not equal the sum of $k$ (not necessarily distinct) elements of $A$ unless $h=k$ and the two sums contain the same terms in some order. A {\it weakly $t$ -independent} set satisfies this property for sums of distinct terms. We give some exact values and asymptotic bounds for the size of a largest $t$ -independent set and weakly $t$ -independent set in abelian groups, particularly in the cyclic group ${\mathbb Z}_n$ .

preprint2013arXiv

On the minimum size of restricted sumsets in cyclic groups

For positive integers $n$ , $m$ , and $h$ , we let $ρ\hat{\;}(\mathbb{Z}_n, m, h)$ denote the minimum size of the $h$ -fold restricted sumset among all $m$ -subsets of the cyclic group of order $n$ . The value of $ρ\hat{\;}(\mathbb{Z}_n, m, h)$ was conjectured for prime values of $n$ and $h=2$ by Erdős and Heilbronn in the 1960s; Dias da Silva and Hamidoune proved the conjecture in 1994 and generalized it for an arbitrary $h$ , but little is known about the case when $n$ is composite. Here we exhibit an explicit upper bound for all $n$ , $m$ , and $h$ ; our bound is tight for all known cases (including all $n$ , $m$ , and $h$ with $n \leq 40$ ). We also provide counterexamples for conjectures made by Plagne and by Hamidoune, Lladó, and Serra.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Béla Bajnok

Research overview

Is this your work?

10 publications

On two questions about restricted sumsets in finite abelian groups

A Constructive Finite Field Method for Scattering Points on the Surface of $d$ -Dimensional Spheres

Comments on Y. O. Hamidoune's Paper "Adding Distinct Congruence Classes"

On Euclidean $t$ -designs

On the Minimum Width of a Cutset in the Truncated Boolean Lattice

On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice

Spherical Designs and Generalized Sum-Free Sets in Abelian Groups

The "Thirty-seven Percent Rule" and the Secretary Problem with Relative Ranks

The independence number of a subset of an abelian group

On the minimum size of restricted sumsets in cyclic groups

See the researcher in context

Building this map preview

Béla Bajnok

Research overview

Is this your work?

10 publications

On two questions about restricted sumsets in finite abelian groups

A Constructive Finite Field Method for Scattering Points on the Surface of ddd-Dimensional Spheres

Comments on Y. O. Hamidoune's Paper "Adding Distinct Congruence Classes"

On Euclidean ttt-designs

On the Minimum Width of a Cutset in the Truncated Boolean Lattice

On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice

Spherical Designs and Generalized Sum-Free Sets in Abelian Groups

The "Thirty-seven Percent Rule" and the Secretary Problem with Relative Ranks

The independence number of a subset of an abelian group

On the minimum size of restricted sumsets in cyclic groups

See the researcher in context

Building this map preview

A Constructive Finite Field Method for Scattering Points on the Surface of $d$ -Dimensional Spheres

On Euclidean $t$ -designs