Source author record

Joshua N. Cooper

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

ResearcherUnclaimed source record

math.CO math.NT

Catalog footprint

Research overview

3works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Constraints on Brouwer's Laplacian Spectrum Conjecture

Brouwer's Conjecture states that, for any graph $G$ , the sum of the $k$ largest (combinatorial) Laplacian eigenvalues of $G$ is at most $|E(G)| + \binom{k+1}{2}$ , $1 \leq k \leq n$ . We present several interrelated results establishing Brouwer's conjecture $\text{BC}_k(G)$ for a wide range of graphs $G$ and parameters $k$ . In particular, we show that (1) $\text{BC}_k(G)$ is true for low-arboricity graphs, and in particular for planar $G$ when $k \geq 11$ ; (2) $\text{BC}_k(G)$ is true whenever the variance of the degree sequence is not very high, generalizing previous results for $G$ regular or random; (3) $\text{BC}_k(G)$ is true if $G$ belongs to a hereditarily spectrally-bounded class and $k$ is sufficiently large as a function of $k$ , in particular $k \geq \sqrt{32n}$ for bipartite graphs; (4) $\text{BC}_k(G)$ holds unless $G$ has edge-edit distance $< k \sqrt{2n} = O(n^{3/2})$ from a split graph; (5) no $G$ violates the conjectured upper bound by more than $O(n^{5/4})$ , and bipartite $G$ by no more than $O(n)$ ; and (6) $\text{BC}_k(G)$ holds for all $k$ outside an interval of length $O(n^{3/4})$ . Furthermore, we present a surprising negative result: asymptotically almost surely, a uniform random signed complete graph violates the conjectured bound by $Ω(n)$ .

preprint2011arXiv

Greedy Galois Games

We show that two duelers with similar, lousy shooting skills (a.k.a. Galois duelers) will choose to take turns firing in accordance with the famous Thue-Morse sequence if they greedily demand their chances to fire as soon as the other's a priori probability of winning exceeds their own. This contrasts with a result from the approximation theory of complex functions that says what more patient duelers would do, if they really cared about being as fair as possible. We note a consequent interpretation of the Thue-Morse sequence in terms of certain expansions in fractional bases close to, but greater than, 1.

preprint2005arXiv

Reciprocals of Binary Power Series

If A is a set of nonnegative integers containing 0, then there is a unique nonempty set B of nonnegative integers such that every positive integer can be written in the form a+b, where a\in A and b\in B, in an even number of ways. We compute the natural density of B for several specific sets A, including the Prouhet-Thue-Morse sequence, {0} \cup {2^n : n \geq 0}, and random sets, and we also study the distribution of densities of B for finite sets A. This problem is motivated by Euler's observation that if A is the set of n that have an odd number of partitions, then B is the set of pentagonal numbers {n(3n+1)/2 : n \in Z}. We also elaborate the connection between this problem and the theory of de Bruijn sequences and linear shift registers.

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.