Search for: All records

Abstract Given a multigraph$$G=(V,E)$$, the edge-coloring problem (ECP) is to color the edges ofGwith the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is referred to as the fractional edge-coloring problem (FECP). The optimal value of ECP (resp. FECP) is called the chromatic index (resp. fractional chromatic index) ofG, denoted by$$\chi '(G)$$(resp.$$\chi ^*(G)$$). Let$$\Delta (G)$$be the maximum degree ofGand let$$\Gamma (G)$$be the density ofG, defined by$$\begin{aligned} \Gamma (G)=\max \left\{ \frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hspace{5.69054pt}\textrm{and} \hspace{5.69054pt}\textrm{odd} \right\} , \end{aligned}$$whereE(U) is the set of all edges ofGwith both ends inU. Clearly,$$\max \{\Delta (G), \, \lceil \Gamma (G) \rceil \}$$is a lower bound for$$\chi '(G)$$. As shown by Seymour,$$\chi ^*(G)=\max \{\Delta (G), \, \Gamma (G)\}$$. In the early 1970s Goldberg and Seymour independently conjectured that$$\chi '(G) \le \max \{\Delta (G)+1, \, \lceil \Gamma (G) \rceil \}$$. Over the past five decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated an important body of work. In this paper we present a proof of this conjecture. Our result implies that, first, there are only two possible values for$$\chi '(G)$$, so an analogue to Vizing’s theorem on edge-colorings of simple graphs holds for multigraphs; second, although it isNP-hard in general to determine$$\chi '(G)$$, we can approximate it within one of its true value, and find it exactly in polynomial time when$$\Gamma (G)>\Delta (G)$$; third, every multigraphGsatisfies$$\chi '(G)-\chi ^*(G) \le 1$$, and thus FECP has a fascinating integer rounding property. 

Harnessing instabilities of multicomponent multistable structural assemblies can potentially lead to scalable and reversible functionalities, which can be enhanced by exploring frustration. For instance, standard Kresling origami cells exhibit nontunable intrinsic energy landscapes determined by their geometry and material properties, limiting their adaptability after fabrication. To overcome this limitation, we introduce frustration to enable fine-tuning of the energy landscape and resulting deformation states. By prestressing the Kresling cell by means of special springs with individual control, we induce either global or localized (i.e., crease level) frustration, which allows changing the energy barrier (cell or assembly). We investigate the mechanical behavior of frustrated Kresling assemblies, both theoretically and experimentally, under various loading and boundary conditions. Our findings reveal that changing the frustration state leads to precise control of folding sequences, enabling previously inaccessible folding paths. The proposed concept paves the way for applications in mechanical metamaterials and other fields requiring highly programmable and reconfigurable systems – e.g., prosthetic limbs. 

We investigate the dynamics of a pair of rigid rotating helices in a viscous fluid, as a model for bacterial flagellar bundle and a prototype of microfluidic pumps. Combining experiments with hydrodynamic modelling, we examine how spacing and phase difference between the two helices affect their torque, flow field and fluid transport capacity at low Reynolds numbers. Hydrodynamic coupling reduces the torque when the helices rotate in phase at constant angular speed, but increases the torque when they rotate out of phase. We identify a critical phase difference, at which the hydrodynamic coupling vanishes despite the close spacing between the helices. A simple model, based on the flow characteristics and positioning of a single helix, is constructed, which quantitatively predicts the torque of the helical pair in both unbounded and confined systems. Finally, we show the influence of spacing and phase difference on the axial flux and the pump efficiency of the helices. Our findings shed light on the function of bacterial flagella and provide design principles for efficient low-Reynolds-number pumps. 

Degradable polymers are promising materials for use to reduce plastic waste and advance biomedical applications. However, to meet the demands of specific applications, tailoring the properties of degradable polymers through precise modification of their chemical structures is critical. Herein, we present a new class of degradable and functionalizable polyacetals synthesized by the ring-opening metathesis copolymerization (ROMP) of two commercially available monomers: dimethyl oxanorbornadiene-2,3-dicarboxylate (OND) and 4,7-dihydro-1,3-dioxepin (DXP). The resulting polyacetals are not only acid-degradable but also readily and efficiently functionalizable via thia–Michael addition, yielding degradable polymer materials with various functional groups and tunable thermal properties. 

We propose a framework for adaptive data collection aimed at robust learning in multi-distribution scenarios under a fixed data collection budget. In each round, the algorithm selects a distribution source to sample from for data collection and updates the model parameters accordingly. The objective is to find the model parameters that minimize the expected loss across all the data sources. Our approach integrates upper-confidence-bound (UCB) sampling with online gradient descent (OGD) to dynamically collect and annotate data from multiple sources. By bridging online optimization and multi-armed bandits, we provide theoretical guarantees for our UCB-OGD approach, demonstrating that it achieves a minimax regret of O(T 1 2 (K ln T) 1 2 ) over K data sources after T rounds. We further provide a lower bound showing that the result is optimal up to a ln T factor. Extensive evaluations on standard datasets and a real-world testbed for object detection in smartcity intersections validate the consistent performance improvements of our method compared to baselines such as random sampling and various active learning methods. 

In neuroscience, delayed synaptic activity plays a pivotal and pervasive role in influencing synchronization, oscillation, and information-processing properties of neural networks. In small rhythm-generating networks, such as central pattern generators (CPGs), time-delays may regulate and determine the stability and variability of rhythmic activity, enabling organisms to adapt to environmental changes, and coordinate diverse locomotion patterns in both function and dysfunction. Here, we examine the dynamics of a three-cell CPG model in which time-delays are introduced into reciprocally inhibitory synapses between constituent neurons. We employ computational analysis to investigate the multiplicity and robustness of various rhythms observed in such multi-modal neural networks. Our approach involves deriving exhaustive two-dimensional Poincaré return maps for phase-lags between constituent neurons, where stable fixed points and invariant curves correspond to various phase-locked and phase-slipping/jitter rhythms. These rhythms emerge and disappear through various local (saddle-node, torus) and non-local (homoclinic) bifurcations, highlighting the multi-functionality (modality) observed in such small neural networks with fast inhibitory synapses.