Source author record

Benjamin Bond

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

ResearcherUnclaimed source record

math.CO cond-mat.stat-mech Formal Languages and Automata Theory

Catalog footprint

Research overview

4works

3topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Abelian networks I. Foundations and examples

In Deepak Dhar's model of abelian distributed processors, automata occupy the vertices of a graph and communicate via the edges. We show that two simple axioms ensure that the final output does not depend on the order in which the automata process their inputs. A collection of automata obeying these axioms is called an "abelian network". We prove a least action principle for abelian networks. As an application, we show how abelian networks can solve certain linear and nonlinear integer programs asynchronously. In most previously studied abelian networks, the input alphabet of each automaton consists of a single letter; in contrast, we propose two non-unary examples of abelian networks: "oil and water" and "abelian mobile agents".

preprint2015arXiv

Abelian networks II. Halting on all inputs

Abelian networks are systems of communicating automata satisfying a local commutativity condition. We show that a finite irreducible abelian network halts on all inputs if and only if all eigenvalues of its production matrix lie in the open unit disk.

preprint2015arXiv

Abelian networks III. The critical group

The critical group of an abelian network is a finite abelian group that governs the behavior of the network on large inputs. It generalizes the sandpile group of a graph. We show that the critical group of an irreducible abelian network acts freely and transitively on recurrent states of the network. We exhibit the critical group as a quotient of a free abelian group by a subgroup containing the image of the Laplacian, with equality in the case that the network is rectangular. We generalize Dhar's burning algorithm to abelian networks, and estimate the running time of an abelian network on an arbitrary input up to a constant additive error.

preprint2012arXiv

EKR sets for large $n$ and $r$

Let $\A\subset\binom{[n]}{r}$ be a compressed, intersecting family and let $X\subset[n]$ . Let $\A(X)={A\in\A:A\cap X\ne\emptyset}$ and $§_{n,r}=\binom{[n]}{r}({1})$ . Motivated by the Erdős-Ko-Rado theorem, Borg asked for which $X\subset[2,n]$ do we have $|\A(X)|\le|§_{n,r}(X)|$ for all compressed, intersecting families $\A$? We call $X$ that satisfy this property EKR. Borg classified EKR sets $X$ such that $|X|\ge r$ . Barber classified $X$ , with $|X|\le r$ , such that $X$ is EKR for sufficiently large $n$ , and asked how large $n$ must be. We prove $n$ is sufficiently large when $n$ grows quadratically in $r$ . In the case where $\A$ has a maximal element, we are able to sharpen this bound to $n>φ^{2}r$ implies $|\A(X)|\le|§_{n,r}(X)|$. We conclude by giving a generating function that speeds up computation of $|\A(X)|$ in comparison with the naïve methods.

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.

Benjamin Bond

Research overview

Is this your work?

4 publications

Abelian networks I. Foundations and examples

Abelian networks II. Halting on all inputs

Abelian networks III. The critical group

EKR sets for large $n$ and $r$

See the researcher in context

Building this map preview

Benjamin Bond

Research overview

Is this your work?

4 publications

Abelian networks I. Foundations and examples

Abelian networks II. Halting on all inputs

Abelian networks III. The critical group

EKR sets for large nnn and rrr

See the researcher in context

Building this map preview

EKR sets for large $n$ and $r$