Source author record

Jake Wellens

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

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Regarding two conjectures on clique and biclique partitions

For a graph $G$ , let $cp(G)$ denote the minimum number of cliques of $G$ needed to cover the edges of $G$ exactly once. Similarly, let $bp_k(G)$ denote the minimum number of bicliques (i.e. complete bipartite subgraphs of $G$ ) needed to cover each edge of $G$ exactly $k$ times. We consider two conjectures -- one regarding the maximum possible value of $cp(G) + cp(\overline{G})$ (due to de Caen, Erdős, Pullman and Wormald) and the other regarding $bp_k(K_n)$ (due to de Caen, Gregory and Pritikin). We disprove the first, obtaining improved lower and upper bounds on $\max_G cp(G) + cp(\overline{G})$ , and we prove an asymptotic version of the second, showing that $bp_k(K_n) = (1+o(1))n$ .

preprint2020arXiv

Testing Gap k-planarity is NP-complete

For all $k \geq 1$ , we show that deciding whether a graph is $k$ -planar is NP-complete, extending the well-known fact that deciding 1-planarity is NP-complete. Furthermore, we show that the gap version of this decision problem is NP-complete. In particular, given a graph with local crossing number either at most $k\ge 1$ or at least $2k$ , we show that it is NP-complete to decide whether the local crossing number is at most $k$ or at least $2k$ . This algorithmic lower bound proves the non-existence of a $(2-ε)$ -approximation algorithm for any fixed $k \ge 1$ . In addition, we analyze the sometimes competing relationship between the local crossing number (maximum number of crossings per edge) and crossing number (total number of crossings) of a drawing. We present results regarding the non-existence of drawings that simultaneously approximately minimize both the local crossing number and crossing number of a graph.

preprint2014arXiv

Sets Characterized by Missing Sums and Differences in Dilating Polytopes

A sum-dominant set is a finite set $A$ of integers such that $|A+A| > |A-A|$ . As a typical pair of elements contributes one sum and two differences, we expect sum-dominant sets to be rare in some sense. In 2006, however, Martin and O'Bryant showed that the proportion of sum-dominant subsets of $\{0,\dots,n\}$ is bounded below by a positive constant as $n\to\infty$ . Hegarty then extended their work and showed that for any prescribed $s,d\in\mathbb{N}_0$ , the proportion $ρ^{s,d}_n$ of subsets of $\{0,\dots,n\}$ that are missing exactly $s$ sums in $\{0,\dots,2n\}$ and exactly $2d$ differences in $\{-n,\dots,n\}$ also remains positive in the limit. We consider the following question: are such sets, characterized by their sums and differences, similarly ubiquitous in higher dimensional spaces? We generalize the integers in a growing interval to the lattice points in a dilating polytope. Specifically, let $P$ be a polytope in $\mathbb{R}^D$ with vertices in $\mathbb{Z}^D$ , and let $ρ_n^{s,d}$ now denote the proportion of subsets of $L(nP)$ that are missing exactly $s$ sums in $L(nP)+L(nP)$ and exactly $2d$ differences in $L(nP)-L(nP)$ . As it turns out, the geometry of $P$ has a significant effect on the limiting behavior of $ρ_n^{s,d}$ . We define a geometric characteristic of polytopes called local point symmetry, and show that $ρ_n^{s,d}$ is bounded below by a positive constant as $n\to\infty$ if and only if $P$ is locally point symmetric. We further show that the proportion of subsets in $L(nP)$ that are missing exactly $s$ sums and at least $2d$ differences remains positive in the limit, independent of the geometry of $P$ . A direct corollary of these results is that if $P$ is additionally point symmetric, the proportion of sum-dominant subsets of $L(nP)$ also remains positive in the limit.

preprint2014arXiv

Sums and differences of correlated random sets

Many fundamental questions in additive number theory (such as Goldbach's conjecture, Fermat's last theorem, and the Twin Primes conjecture) can be expressed in the language of sum and difference sets. As a typical pair of elements contributes one sum and two differences, we expect that $|A-A| > |A+A|$ for a finite set $A$ . However, in 2006 Martin and O'Bryant showed that a positive proportion of subsets of $\{0, \dots, n\}$ are sum-dominant, and Zhao later showed that this proportion converges to a positive limit as $n \to \infty$ . Related problems, such as constructing explicit families of sum-dominant sets, computing the value of the limiting proportion, and investigating the behavior as the probability of including a given element in $A$ to go to zero, have been analyzed extensively. We consider many of these problems in a more general setting. Instead of just one set $A$ , we study sums and differences of pairs of \emph{correlated} sets $(A,B)$ . Specifically, we place each element $a \in \{0,\dots, n\}$ in $A$ with probability $p$ , while $a$ goes in $B$ with probability $ρ_1$ if $a \in A$ and probability $ρ_2$ if $a \not \in A$ . If $|A+B| > |(A-B) \cup (B-A)|$ , we call the pair $(A,B)$ a \emph{sum-dominant $(p,ρ_1, ρ_2)$ -pair}. We prove that for any fixed $\vecρ=(p, ρ_1, ρ_2)$ in $(0,1)^3$ , $(A,B)$ is a sum-dominant $(p,ρ_1, ρ_2)$ -pair with positive probability, and show that this probability approaches a limit $P(\vecρ)$ . Furthermore, we show that the limit function $P(\vecρ)$ is continuous. We also investigate what happens as $p$ decays with $n$ , generalizing results of Hegarty-Miller on phase transitions. Finally, we find the smallest sizes of MSTD pairs.

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.