Episciences.org
Not a member yet
6707 research outputs found
Sort by
A complete invariant for doodles on a 2-sphere
No full textWe define a complete invariant for doodles on a 2-sphere which takes valuesin series of chord diagrams of certain type. The coefficients at the diagramswith chords are finite type invariants of doodles of order at most .Comment: 13 pages, many figure
Simple conditions for the transformation of dynamical coordinates into canonical ones in Hamiltonian dynamics
No full textWe obtain conditions, which when fulfilled, permit to transform the coordinates of a dynamical system into pairs of canonical ones for some Hamiltonian system. These conditions, restricted to the class of coordinate transformations which act on each coordinate independently, are greatly simplified. However, they are surprisingly successful in defining canonical coordinates and an associated Hamiltonian for several test examples. So, a method is proposed to exploit these simple transformations in a systematic manner
Varieties of unary-determined distributive -magmas and bunched implication algebras
No full textA distributive lattice-ordered magma (-magma) is a distributive lattice with a binary operation that preserves joinsin both arguments, and when is associative then is anidempotent semiring. A -magma with a top is unary-determined if . Thesealgebras are term-equivalent to a subvariety of distributive lattices with and two join-preserving unary operations . Weobtain simple conditions on such that is associative, commutative,idempotent and/or has an identity element. This generalizes previous results on the structure of doubly idempotentsemirings and, in the case when the distributive lattice is a Heyting algebra,it provides structural insight into unary-determined algebraic models ofbunched implication logic. We also provide Kripke semantics for the algebrasunder consideration, which leads to more efficient algorithms for constructingfinite models. We find all subdirectly irreducible algebras up to cardinalityeight in which is a closure operator, as well as allfinite unary-determined bunched implication chains and map out the poset ofjoin-irreducible varieties generated by them
Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
No full textThe Grundy number of a graph is the maximum number of colours used by the"First-Fit" greedy colouring algorithm over all vertex orderings. Given avertex ordering , the "First-Fit" greedy colouringalgorithm colours the vertices in the order of by assigning to eachvertex the smallest colour unused in its neighbourhood. By restricting this procedure to vertex orderings that are connected, weobtain {\em connected greedy colourings}. For some graphs, all connected greedycolourings use exactly colours; they are called {\em good graphs}. Onthe opposite, some graphs do not admit any connected greedy colouring usingonly colours; they are called {\em ugly graphs}. We show that no perfect graph is ugly. We also give simple proofs of thisfact for subclasses of perfect graphs (block graphs, comparability graphs), andshow that no -minor free graph is ugly. Moreover, our proofs are constructive, and imply the existence ofpolynomial-time algorithms to compute good connected orderings for these graphclasses.Comment: 14 pages, 5 figure
Cayley Linear-Time Computable Groups
No full textThis paper looks at the class of groups admitting normal forms for which theright multiplication by a group element is computed in linear time on amulti-tape Turing machine. We show that the groups , and Thompson's group havenormal forms for which the right multiplication by a group element is computedin linear time on a -tape Turing machine. This refines the resultspreviously established by Elder and the authors that these groups are Cayleypolynomial-time computable.Comment: Published in journal of Groups, Complexity, Cryptolog
From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism
No full textWe study transformations of automata and games using Muller conditions intoequivalent ones using parity or Rabin conditions. We present twotransformations, one that turns a deterministic Muller automaton into anequivalent deterministic parity automaton, and another that provides anequivalent history-deterministic Rabin automaton. We show a strong optimalityresult: the obtained automata are minimal amongst those that can be derivedfrom the original automaton by duplication of states. We introduce the notionsof locally bijective morphisms and history-deterministic mappings to formalisethe correctness and optimality of these transformations. The proposed transformations are based on a novel structure, called thealternating cycle decomposition, inspired by and extending Zielonka trees. Inaddition to providing optimal transformations of automata, the alternatingcycle decomposition offers fundamental information on their structure. We usethis information to give crisp characterisations on the possibility ofrelabelling automata with different acceptance conditions and to perform asystematic study of a normal form for parity automata.Comment: Extended version of an ICALP 2021 paper. It also includes content from an ICALP 2022 paper. Version 3: Journal version for TheoretiC
Algebraic cycles on Gushel-Mukai varieties
No full textWe study algebraic cycles on complex Gushel-Mukai (GM) varieties. We provethe generalised Hodge conjecture, the (motivated) Mumford-Tate conjecture, andthe generalised Tate conjecture for all GM varieties. We compute all integralChow groups of GM varieties, except for the only two infinite-dimensional cases(1-cycles on GM fourfolds and 2-cycles on GM sixfolds). We prove that if two GMvarieties are generalised partners or generalised duals, their rational Chowmotives in middle degree are isomorphic.Comment: 23 pages, final version, in special volume in honour of C. Voisi
A note on removable edges in near-bricks
No full textAn edge of a matching covered graph is removable if is alsomatching covered. Carvalho, Lucchesi, and Murty showed that every brick different from and has at least removableedges, where is the maximum degree of . In this paper, wegeneralize the result to irreducible near-bricks, where a graph is irreducibleif it contains no single ear of length three or more
Extending partial edge colorings of iterated cartesian products of cycles and paths
No full textWe consider the problem of extending partial edge colorings of iteratedcartesian products of even cycles and paths, focusing on the case when theprecolored edges satisfy either an Evans-type condition or is a matching. Inparticular, we prove that if is the th power of the cartesianproduct of the even cycle with itself, and at most edges of are precolored, then there is a proper -edge coloring of that agreeswith the partial coloring. We show that the same conclusion holds, withoutrestrictions on the number of precolored edges, if any two precolored edges areat distance at least from each other. For odd cycles of length at least, we prove that if is the th power of the cartesianproduct of the odd cycle with itself (), and at most edges of are precolored, then there is a proper -edge coloring of that agrees with the partial coloring. Our results generalize previous oneson precoloring extension of hypercubes [Journal of Graph Theory 95 (2020)410--444].Comment: Final version, published in DMTC
Spectral Independence via Stability and Applications to Holant-Type Problems
No full textThis paper formalizes connections between stability of polynomials andconvergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove thatif a (multivariate) partition function is nonzero in a region around a realpoint then spectral independence holds at . As aconsequence, for Holant-type problems (e.g., spin systems) on bounded-degreegraphs, we obtain optimal mixing time bounds for the single-siteupdate Markov chain known as the Glauber dynamics. Our result significantlyimproves the running time guarantees obtained via the polynomial interpolationmethod of Barvinok (2017), refined by Patel and Regts (2017). There are a variety of applications of our results. In this paper, we focuson Holant-type (i.e., edge-coloring) problems, including weighted edge coversand weighted even subgraphs. For the weighted edge cover problem (and severalnatural generalizations) we obtain an sampling algorithm onbounded-degree graphs. The even subgraphs problem corresponds to thehigh-temperature expansion of the ferromagnetic Ising model. We obtain an sampling algorithm for the ferromagnetic Ising model with anonzero external field on bounded-degree graphs, which improves upon theclassical result of Jerrum and Sinclair (1993) for this class of graphs. Weobtain further applications to antiferromagnetic two-spin models on linegraphs, weighted graph homomorphisms, tensor networks, and more.Comment: Journal Version for TheoretiC