More Like this

1. The orbit-polynomial: a novel measure of symmetry in networks

   https://doi.org/10.1109/ACCESS.2020.2970059  

   Dehmer, M. ; Chen, Z. ; Emmert-Streib, F. ; Mowshowitz, A. ; Varmuza, K. ; Feng, L. ; Jodlbauer, H. ; Shi, Y. ; and Tao, J. ( January 2020 , IEEE access)

   Research on the structural complexity of networks has produced many useful results in graph theory and applied disciplines such as engineering and data analysis. This paper is intended as a further contribution to this area of research. Here we focus on measures designed to compare graphs with respect to symmetry. We do this by means of a novel characteristic of a graph G, namely an ``orbit polynomial.'' A typical term of this univariate polynomial is of the form czn, where c is the number of orbits of size n of the automorphism group of G. Subtracting the orbit polynomial frommore »1 results in another polynomial that has a unique positive root, which can serve as a relative measure of the symmetry of a graph. The magnitude of this root is indicative of symmetry and can thus be used to compare graphs with respect to that property. In what follows, we will prove several inequalities on the unique positive roots of orbit polynomials corresponding to different graphs, thus showing differences in symmetry. In addition, we present numerical results relating to several classes of graphs for the purpose of comparing the new symmetry measure with existing ones. Finally, it is applied to a set of isomers of the chemical compound adamantane C10H16. We believe that the measure can be quite useful for tackling applications in chemistry, bioinformatics, and structure-oriented drug design.« less
2. On the Hardness and Inapproximability of Recognizing Wheeler Graphs

   https://doi.org/10.4230/LIPIcs.ESA.2019.51  

   Gibney, Daniel ;  Thankachan, Sharma V. ( January 2019 , 27th Annual European Symposium on Algorithms (ESA) 2019)

   In recent years several compressed indexes based on variants of the Burrows-Wheeler transformation have been introduced. Some of these are used to index structures far more complex than a single string, as was originally done with the FM-index [Ferragina and Manzini, J. ACM 2005]. As such, there has been an increasing effort to better understand under which conditions such an indexing scheme is possible. This has led to the introduction of Wheeler graphs [Gagie et al., Theor. Comput. Sci., 2017]. Gagie et al. showed that de Bruijn graphs, generalized compressed suffix arrays, and several other BWT related structures can bemore »represented as Wheeler graphs and that Wheeler graphs can be indexed in a way which is space-efficient. Hence, being able to recognize whether a given graph is a Wheeler graph, or being able to approximate a given graph by a Wheeler graph, could have numerous applications in indexing. Here we resolve the open question of whether there exists an efficient algorithm for recognizing if a given graph is a Wheeler graph. We present - The problem of recognizing whether a given graph G=(V,E) is a Wheeler graph is NP-complete for any edge label alphabet of size sigma >= 2, even when G is a DAG. This holds even on a restricted, subset of graphs called d-NFA's for d >= 5. This is in contrast to recent results demonstrating the problem can be solved in polynomial time for d-NFA's where d <= 2. We also show the recognition problem can be solved in linear time for sigma =1; - There exists an 2^{e log sigma + O(n + e)} time exact algorithm where n = |V| and e = |E|. This algorithm relies on graph isomorphism being computable in strictly sub-exponential time; - We define an optimization variant of the problem called Wheeler Graph Violation, abbreviated WGV, where the aim is to remove the minimum number of edges in order to obtain a Wheeler graph. We show WGV is APX-hard, even when G is a DAG, implying there exists a constant C >= 1 for which there is no C-approximation algorithm (unless P = NP). Also, conditioned on the Unique Games Conjecture, for all C >= 1, it is NP-hard to find a C-approximation; - We define the Wheeler Subgraph problem, abbreviated WS, where the aim is to find the largest subgraph which is a Wheeler Graph (the dual of the WGV). In contrast to WGV, we prove that the WS problem is in APX for sigma=O(1); The above findings suggest that most problems under this theme are computationally difficult. However, we identify a class of graphs for which the recognition problem is polynomial-time solvable, raising the open question of which parameters determine this problem's difficulty.« less
3. The extraplanar type II supernova ASASSN-14jb in the nearby edge-on galaxy ESO 467-G051

   https://doi.org/10.1051/0004-6361/201834972  

   Meza, Nicolás ; Prieto, J. L. ; Clocchiatti, A. ; Galbany, L. ; Anderson, J. P. ; Falco, E. ; Kochanek, C. S. ; Kuncarayakti, H. ; Sánchez, S. F. ; Brimacombe, J. ; et al ( September 2019 , Astronomy & Astrophysics)

   We present optical photometry and spectroscopy of the Type II supernova ASASSN-14jb, together with Very Large Telescope (VLT) Multi Unit Spectroscopic Explorer (MUSE) integral field observations of its host galaxy and a nebular-phase spectrum. This supernova, in the nearby galaxy ESO 467-G051 ( z  = 0.006), was discovered and followed-up by the all-sky automated survey for supernovae (ASAS-SN). We obtained well-sampled las cumbres network (LCOGTN) B V g r i and Swift w 2 m 1 w 1 u b v optical, near-UV/optical light curves, and several optical spectra in the early photospheric phases. The transient ASASSN-14jb exploded ∼2 kpc abovemore »the star-forming disk of ESO 467-G051, an edge-on disk galaxy. The large projected distance from the disk of the supernova position and the non-detection of any H II region in a 1.4 kpc radius in projection are in conflict with the standard environment of core-collapse supernova progenitors and suggests the possible scenario that the progenitor received a kick in a binary interaction. We present analysis of the optical light curves and spectra, from which we derived a distance of 25 ± 2 Mpc using state-of-the-art empirical methods for Type II SNe, physical properties of the SN explosion ( 56 Ni mass, explosion energy, and ejected mass), and properties of the progenitor; namely the progenitor radius, mass, and metallicity. Our analysis yields a 56 Ni mass of 0.0210  ±  0.0025  M ⊙ , an explosion energy of ≈0.25 × 10 51 ergs, and an ejected mass of ≈6  M ⊙ . We also constrained the progenitor radius to be R *  = 580  ±  28  R ⊙ which seems to be consistent with the sub-Solar metallicity of 0.3  ±  0.1  Z ⊙ derived from the supernova Fe II λ 5018 line. The nebular spectrum constrains strongly the progenitor mass to be in the range 10–12 M ⊙ . From the Spitzer data archive we detect ASASSN-14jb ≈330 days past explosion and we derived a total dust mass of 10 −4   M ⊙ from the 3.6 μ m and 4.5 μ m photometry. Using the F U V , N U V , B V g r i , K s , 3.6 μ m, and 4.5 μ m total magnitudes for the host galaxy, we fit stellar population synthesis models, which give an estimate of M *  ≈ 1 × 10 9   M ⊙ , an age of 3.2 Gyr, and a SFR ≈0.07  M ⊙ yr −1 . We also discuss the low oxygen abundance of the host galaxy derived from the MUSE data, having an average of 12 + log(O/H) = 8.27 +0.16 −0.20 using the O 3 N 2 diagnostic with strong line methods. We compared it with the supernova spectra, which is also consistent with a sub-Solar metallicity progenitor. Following recent observations of extraplanar H II regions in nearby edge-on galaxies, we derived the metallicity offset from the disk, being positive, but consistent with zero at 2 σ , suggesting enrichment from disk outflows. We finally discuss the possible scenarios for the unusual environment for ASASSN-14jb and conclude that either the in-situ star formation or runaway scenario would imply a low-mass progenitor, agreeing with our estimate from the supernova nebular spectrum. Regardless of the true origin of ASASSN-14jb, we show that the detailed study of the environment roughly agree with the stronger constraints from the observation of the transient.« less
4. Triforce and corners

   https://doi.org/10.1017/s0305004119000173  

   FOX, JACOB ; SAH, ASHWIN ; SAWHNEY, MEHTAAB ; STONER, DAVID ; ZHAO, YUFEI ( July 2020 , Mathematical Proceedings of the Cambridge Philosophical Society)

   Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $G = {\mathbb{F}}_2^n$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number ofmore »“corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.« less
5. The Milky Way bar and bulge revealed by APOGEE and Gaia EDR3

   https://doi.org/10.1051/0004-6361/202039030  

   Queiroz, A. B. ; Chiappini, C. ; Perez-Villegas, A. ; Khalatyan, A. ; Anders, F. ; Barbuy, B. ; Santiago, B. X. ; Steinmetz, M. ; Cunha, K. ; Schultheis, M. ; et al ( December 2021 , Astronomy & Astrophysics)

   We investigate the inner regions of the Milky Way using data from APOGEE and Gaia EDR3. Our inner Galactic sample has more than 26 500 stars within | X Gal |< 5 kpc, | Y Gal |< 3.5 kpc, | Z Gal |< 1 kpc, and we also carry out the analysis for a foreground-cleaned subsample of 8000 stars that is more representative of the bulge–bar populations. These samples allow us to build chemo-dynamical maps of the stellar populations with vastly improved detail. The inner Galaxy shows an apparent chemical bimodality in key abundance ratios [ α /Fe], [C/N], andmore »[Mn/O], which probe different enrichment timescales, suggesting a star formation gap (quenching) between the high- and low- α populations. Using a joint analysis of the distributions of kinematics, metallicities, mean orbital radius, and chemical abundances, we can characterize the different populations coexisting in the innermost regions of the Galaxy for the first time. The chemo-kinematic data dissected on an eccentricity–| Z | max plane reveal the chemical and kinematic signatures of the bar, the thin inner disc, and an inner thick disc, and a broad metallicity population with large velocity dispersion indicative of a pressure-supported component. The interplay between these different populations is mapped onto the different metallicity distributions seen in the eccentricity–| Z | max diagram consistently with the mean orbital radius and V ϕ distributions. A clear metallicity gradient as a function of | Z | max is also found, which is consistent with the spatial overlapping of different populations. Additionally, we find and chemically and kinematically characterize a group of counter-rotating stars that could be the result of a gas-rich merger event or just the result of clumpy star formation during the earliest phases of the early disc that migrated into the bulge. Finally, based on 6D information, we assign stars a probability value of being on a bar orbit and find that most of the stars with large bar orbit probabilities come from the innermost 3 kpc, with a broad dispersion of metallicity. Even stars with a high probability of belonging to the bar show chemical bimodality in the [ α /Fe] versus [Fe/H] diagram. This suggests bar trapping to be an efficient mechanism, explaining why stars on bar orbits do not show a significant, distinct chemical abundance ratio signature.« less