Search

A family of graphs $\mathcal{F}$ is said to have the joint embedding property (JEP) if for every $G_1, G_2\in \mathcal{F}$, there is an $H\in \mathcal{F}$ that contains both $G_1$ and $G_2$ as induced subgraphs. If $\mathcal{F}$ is given by a finite set $S$ of forbidden induced subgraphs, it is known that determining if $\mathcal{F}$ has JEP is undecidable. We prove that this problem is decidable if $P_4\in S$ and generalize this result to families of rooted labeled trees under topological containment, bounded treewidth families under the graph minor relation, and bounded cliquewidth families under the induced subgraph relation., Comment: 14 pages

We prove that the diameter of a Sidon set (also known as a Babcock sequence, Golomb ruler, or $B_2$ set) with $k$ elements is at least $k^2-b k^{3/2}-O(k)$ where $b\le 1.96365$, a comparatively large improvement on past results. Equivalently, a Sidon set with diameter $n$ has at most $n^{1/2}+0.98183n^{1/4}+O(1)$ elements. The proof is conceptually simple but very computationally intensive, and the proof uses substantial computer assistance. We also provide a proof of $b\le 1.99058$ that can be verified by hand, which still improves on past results. Finally, we prove that $g$-thin Sidon sets (aka $g$-Golomb rulers) with $k$ elements have diameter at least $g^{-1} k^2 - (2-\varepsilon)g^{-1}k^{3/2} - O(k)$, with $\varepsilon\ge 0.02g^{-2}$., Comment: 16 pages, 1 figure

We prove that $\{\overline{K_3}, H\}$-free graphs are not counterexamples to Hadwiger's Conjecture, where $H$ is any one of 33 graphs on seven, eight, or nine vertices, or $H=K_8$. This improves on past results of Plummer-Stiebitz-Toft, Kriesell, and Bosse. The proofs are mostly computer-assisted., Comment: 24 pages, 5 figures

We present two complementary techniques called catalysis and inhibition which allow one to determine if a given pattern is TP completable or TP non-completable, respectively. Empirically, these techniques require considering only one unspecified entry at a time in a vast majority of cases, which makes these techniques ripe for automation and a powerful framework for future work in the TP completion problem. With small modifications, these techniques are also applicable to the TN completion problem. We provide two major applications. First, we characterize all 4-by-4 patterns by completability. There are a total of 78 new obstructions of this size, six times as many as the 3-by-$n$ case for all $n$ combined. Second, we provide a characterization of the so-called 1-variable obstructions in the TN case, which includes as a corollary a characterization of patterns with a single unspecified entry. This also provides a novel partial result towards proving the conjecture that all TN-completable patterns are TP-completable., Comment: 30 pages, 0 figures. Some typos fixed and additional references

We present a proof of Litherland's formula for the Tristram-Levine signature of a satellite knot in terms of its constituents. Litherland's original proof used more advanced algebraic techniques, while ours uses only linear algebra and some basic results in knot theory., Comment: 6 pages, 0 figures. Fixed some typos and added a section comparing our proof to a similar past proof

We prove that checking if a partial matrix is partial totally positive is co-NP-complete. This contrasts with checking a conventional matrix for total positivity, for which we provide a cubic time algorithm. Checking partial sign regularity with any signature, including partial total nonnegativity, is also co-NP-complete. Finally, we prove that checking partial total positivity in a partial matrix with logarithmically many unspecified entries may be done in polynomial time., Comment: 4 pages, 0 figures; added Section 4 and minor corrections

We develop a Multi-Scale Merge-Split Markov chain on redistricting plans. The chain is designed to be usable as the proposal in a Markov Chain Monte Carlo (MCMC) algorithm. Sampling the space of plans amounts to dividing a graph into a partition with a specified number of elements which each correspond to a different district. The districts satisfy a collection of hard constraints and the measure may be weighted with regard to a number of other criteria. The multi-scale algorithm is similar to our previously developed Merge-Split proposal, however, this algorithm provides improved scaling properties and may also be used to preserve nested communities of interest such as counties and precincts. Both works use a proposal which extends the ReCom algorithm which leveraged spanning trees merge and split districts. In this work we extend the state space so that each district is defined by a hierarchy of trees. In this sense, the proposal step in both algorithms can be seen as a "Forest ReCom." We also expand the state space to include edges that link specified districts, which further improves the computational efficiency of our algorithm. The collection of plans sampled by the MCMC algorithm can serve as a baseline against which a particular plan of interest is compared. If a given plan has different racial or partisan qualities than what is typical of the collection of plans, the given plan may have been gerrymandered and is labeled as an outlier.

We develop a new Markov chain on graph partitions that makes relatively global moves yet is computationally feasible to be used as the proposal in the Metropolis-Hastings method. Our resulting algorithm can be made reversible and able to sample from a specified measure on partitions. Both of these properties are critical to some important applications and computational Bayesian statistics in general. Our proposal chain modifies the recently developed method called Recombination (ReCom), which draws spanning trees on joined partitions and then randomly cuts them to repartition. We improve the computational efficiency by augmenting the state space from partitions to spanning forests. The extra information accelerates the computation of the forward and backward proposal probabilities. We demonstrate this method by sampling redistricting plans and find promising convergence results on several key observables of interest., Comment: 29 pages; 14 figures; 3 page appendix

North Carolina's constitution requires that state legislative districts should not split counties. However, counties must be split to comply with the "one person, one vote" mandate of the U.S. Supreme Court. Given that counties must be split, the North Carolina legislature and courts have provided guidelines that seek to reduce counties split across districts while also complying with the "one person, one vote" criteria. Under these guidelines, the counties are separated into clusters. The primary goal of this work is to develop, present, and publicly release an algorithm to optimally cluster counties according to the guidelines set by the court in 2015. We use this tool to investigate the optimality and uniqueness of the enacted clusters under the 2017 redistricting process. We verify that the enacted clusters are optimal, but find other optimal choices. We emphasize that the tool we provide lists \textit{all} possible optimal county clusterings. We also explore the stability of clustering under changing statewide populations and project what the county clusters may look like in the next redistricting cycle beginning in 2020/2021., Comment: 21 pages; 7 figures

We calculate Bayes factors to quantify how the feasibility of the constrained minimal supersymmetric standard model (CMSSM) has changed in the light of a series of observations. This is done in the Bayesian spirit where probability reflects a degree of belief in a proposition and Bayes' theorem tells us how to update it after acquiring new information. Our experimental baseline is the approximate knowledge that was available before LEP, and our comparison model is the Standard Model with a simple dark matter candidate. To quantify the amount by which experiments have altered our relative belief in the CMSSM since the baseline data we compute the Bayes factors that arise from learning in sequence the LEP Higgs constraints, the XENON100 dark matter constraints, the 2011 LHC supersymmetry search results, and the early 2012 LHC Higgs search results. We find that LEP and the LHC strongly shatter our trust in the CMSSM (with $M_0$ and $M_{1/2}$ below 2 TeV), reducing its posterior odds by a factor of approximately two orders of magnitude. This reduction is largely due to substantial Occam factors induced by the LEP and LHC Higgs searches., Comment: 38 pages, 14 figures; version as published in EPJC

In anticipation of data from the Large Hadron Collider (LHC) and the potential discovery of supersymmetry, in this work we seek an answer to the following: What are the chances that supersymmetry will be found at the LHC? Will the LHC data be enough to discover a given supersymmetric model? And what other measurements can assist the LHC establish the presence of supersymmetry? As a step toward answering these general questions, we calculate the odds of the next-to-minimal version of the popular supergravity motivated model (NmSuGra) being discovered at the LHC to be 4:3 (57 %). We also demonstrate that viable regions of the NmSuGra parameter space outside the LHC reach can be covered by upgraded versions of dark matter direct detection experiments, such as super-CDMS, at 99 % confidence level. Due to the similarities of the models, we expect very similar results for the constrained minimal supersymmetric standard model (CMSSM)., Comment: 21 pages, 7 figures

We analyze the discovery potential of the next-to-minimal supergravity motivated model: NmSuGra. This model is an extension of mSuGra by a gauge singlet, and contains only one additional parameter: lambda, the Higgs-singlet-Higgs coupling. NmSuGra solves the mu-problem and reduces the fine tuning of mSuGra. After identifying parameter space regions preferred by present experimental data, we show that these regions of NmSuGra are amenable to detection by the combination of the Large Hadron Collider and an upgraded Cryogenic Dark Matter Search. This conclusion holds strictly provided that the more than three sigma discrepancy in the difference of the experimental and the standard theoretical values of the anomalous magnetic moment of the muon prevails in the future., Comment: 3 pages, 3 figures, proceedings for SUSY08 and DSU08

Applying a likelihood analysis to the next-to-minimal supergravity-motivated model, we identify parameter space regions preferred by present experimental limits from collider, astrophysical, and low energy measurements. We then show that favored regions are amenable to detection by a combination of the CERN Large Hadron Collider and an upgraded Cryogenic Dark Matter Search, provided that the more than three sigma discrepancy in the difference of the experimental and the standard theoretical values of the anomalous magnetic moment of the muon prevails in the future., Comment: Version appeared in Phys. Rev. D