An official website of the United States government
We consider how to generate graphs of arbitrary size whose chromatic numbers can be chosen (or are well-bounded) for testing graph coloring algorithms on parallel computers. For the distance-1 graph coloring problem, we identify three classes of graphs with this property. The first is the Erdős-Rényi random graph with prescribed expected degree, where the chromatic number is known with high probability. It is also known that the Greedy algorithm colors this graph using at most twice the number of colors as the chromatic number. The second is a random geometric graph embedded in hyperbolic space where the size of the maximum clique provides a tight lower bound on the chromatic number. The third is a deterministic graph described by Mycielski, where the graph is recursively constructed such that its chromatic number is known and increases with graph size, although the size of the maximum clique remains two. For Jacobian estimation, we bound the distance-2 chromatic number of random bipartite graphs by considering its equivalence to distance-1 coloring of an intersection graph. We use a “balls and bins” probabilistic analysis to establish a lower bound and an upper bound on the distance-2 chromatic number. The regimes of graph sizes and probabilities that we consider are chosen to suit the Jacobian estimation problem, where the number of columns and rows are asymptotically nearly equal, and have number of nonzeros linearly related to the number of columns. Computationally we verify the theoretical predictions and show that the graphs are often be colored optimally by the serial and parallel Greedy algorithms.
more »
« less
This content will become publicly available on February 15, 2026
Exact enumeration of fullerenes
A fullerene, or buckyball, is a trivalent graph on the sphere with only pentagonal and hexagonal faces. Building on ideas of Thurston, we use modular forms to give an exact formula for the number of oriented fullerenes with a given number of vertices.
more »
« less
- Award ID(s):
- 2441240
- PAR ID:
- 10642973
- Publisher / Repository:
- Duke Mathematical Journal
- Date Published:
- Journal Name:
- Duke Mathematical Journal
- Volume:
- 174
- Issue:
- 3
- ISSN:
- 0012-7094
- Page Range / eLocation ID:
- 575 - 613
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Defects in crosslinked networks have a negative effect on mechanical and functional properties. In this study, an epoxy resin diglycidyl ether of bisphenol A crosslinked by a hardener 4,4-diaminodiphenyl methane with various cyclic topologies was simulated to find correlations between the mechanical/shape memory properties (i.e. glassy/rubbery elastic modulus, shape recovery ratio, and recovery stress) and cyclic topologies (i.e. number of total loops, number of defective loops (DLs), etc). The effect of cyclic topology on shape memory properties was more significant than its effect on mechanical properties, altering recovery stress by more than 25% on average. After analyzing several topological fingerprints such as total number of loops, number of DLs, and number of higher order loops, we found that the effect of cyclic topology on the mechanical/shape memory properties of the systems can be best understood by the fraction of hardeners reacted with four distinct epoxy molecules (tetra-distinctly-reacted (TDR) hardeners). By increasing the number of TDR hardeners, the network is closer to ideal, resulting in an increase in the number of higher order loops and a reduction in the number of DLs, which in turn leads to an increase in rubbery elastic modulus and shape recovery ratio to a lesser degree, but a substantial increase in recovery stress. These results suggest that utilization of experimental techniques such as semibatch monomer addition, which leads to a more expanded and defect-free network, can result in a simultaneous increase in both shape recovery ratio and recovery stress in thermoset shape memory polymers (TSMPs). Moreover, topology alteration can be used to synthesize TSMPs with improved recovery stress without significantly increasing their stiffness.more » « less
-
The underlying genetic changes that regulate the appearance and disappearance of repeated traits, or serial homologs, remain poorly understood. One hypothesis is that variation in genomic regions flanking master regulatory genes, also known as input–output genes, controls variation in trait number, making the locus of evolution almost predictable. Another hypothesis implicates genetic variation in up- or downstream loci of master control genes. Here, we use the butterfly Bicyclus anynana , a species that exhibits natural variation in eyespot number on the dorsal hindwing, to test these two hypotheses. We first estimated the heritability of dorsal hindwing eyespot number by breeding multiple butterfly families differing in eyespot number and regressing eyespot numbers of offspring on midparent values. We then estimated the number and identity of independent genetic loci contributing to eyespot number variation by performing a genome-wide association study with restriction site-associated DNA sequencing from multiple individuals varying in number of eyespots sampled across a freely breeding laboratory population. We found that dorsal hindwing eyespot number has a moderately high heritability of ∼0.50 and is characterized by a polygenic architecture. Previously identified genomic regions involved in eyespot development, and novel ones, display high association with dorsal hindwing eyespot number, suggesting that homolog number variation is likely determined by regulatory changes at multiple loci that build the trait, and not by variation at single master regulators or input–output genes.more » « less
-
The mechanisms driving the transition to turbulence in pulsatile flows are not well understood. Prior studies in this domain have noted the dynamics of this flow regime to depend on the mean Reynolds number, pulsation frequency (i.e., Womersley number), and inflow pulsatile waveform shape. Conflicting findings, particularly regarding the role of the Womersley number on the critical Reynolds number and the development of turbulence, have been reported. The discord has primarily been observed for flows, with Womersley numbers ranging from 4 to 12. Hence, in this work, we use particle image velocimetry to explore the effects of the Womersley number within this 4–12 range on the dynamics of the pulsatile transition. Eighteen test cases were captured using six mean Reynolds numbers (range 800–4200) and five Womersley numbers. Turbulent kinetic energy, turbulence intensity (TI), and phase lag were computed. Our results indicated that the critical Reynolds number was roughly independent of the Womersley number. At high Womersley numbers, the TI trend maintained lower pulsatility, and the flow was observed to mimic a steady transitional flow regime. A plateau of the TI-velocity and TI-acceleration phase lag was observed at a Womersley number of 8, highlighting that this may be the critical value where further increases to the Womersley number do not alter the transition dynamics. Furthermore, this suggests that the phase lag may provide a universal indicator of the specific influence of the Womersley number on transition for a given flow. Overall, these findings elucidate critical details regarding the role of the Womersley number in the transition to turbulence.more » « less
-
Mailler, Cécile; Wild, Sebastian (Ed.)Galled trees appear in problems concerning admixture, horizontal gene transfer, hybridization, and recombination. Building on a recursive enumerative construction, we study the asymptotic behavior of the number of rooted binary unlabeled (normal) galled trees as the number of leaves n increases, maintaining a fixed number of galls g. We find that the exponential growth with n of the number of rooted binary unlabeled normal galled trees with g galls has the same value irrespective of the value of g ≥ 0. The subexponential growth, however, depends on g; it follows c_g n^{2g-3/2}, where c_g is a constant dependent on g. Although for each g, the exponential growth is approximately 2.4833ⁿ, summing across all g, the exponential growth is instead approximated by the much larger 4.8230ⁿ.more » « less
