Search results for "combinatoric"

Roots in the mapping class groups

2006

The purpose of this paper is the study of the roots in the mapping class groups. Let $\Sigma$ be a compact oriented surface, possibly with boundary, let $\PP$ be a finite set of punctures in the interior of $\Sigma$, and let $\MM (\Sigma, \PP)$ denote the mapping class group of $(\Sigma, \PP)$. We prove that, if $\Sigma$ is of genus 0, then each $f \in \MM (\Sigma)$ has at most one $m$-root for all $m \ge 1$. We prove that, if $\Sigma$ is of genus 1 and has non-empty boundary, then each $f \in \MM (\Sigma)$ has at most one $m$-root up to conjugation for all $m \ge 1$. We prove that, however, if $\Sigma$ is of genus $\ge 2$, then there exist $f,g \in \MM (\Sigma, \PP)$ such that $f^2=g^2$, $…

A Mountain Pass Theorem for a Suitable Class of Functions

2009

Computing with Rational Symmetric Functions and Applications to Invariant Theory and PI-algebras

2012

The research of the first named author was partially supported by INdAM. The research of the second, third, and fourth named authors was partially supported by Grant for Bilateral Scientific Cooperation between Bulgaria and Ukraine. The research of the fifth named author was partially supported by NSF Grant DMS-1016086.

Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection

2012

We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…

Maximum weight relaxed cliques and Russian Doll Search revisited

2015

Trukhanov et al. [Trukhanov S, Balasubramaniam C, Balasundaram B, Butenko S (2013) Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Comp. Opt. and Appl., 56(1), 113–130] used the Russian Doll Search (RDS) principle to effectively find maximum hereditary structures in graphs. Prominent examples of such hereditary structures are cliques and some clique relaxations intensely discussed and studied in network analysis. The effectiveness of the tailored RDS by Trukhanov et al. for s-plex and s-defective clique can be attributed to their cleverly designed incremental verification procedures used to distinguish feasible from infeasible struct…

On the chromatic number of disk graphs

1998

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that X(G) ≤ c.ω(G) for a constant c. Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on X(G). We find that their worst-case performance expressed in the number of used colors is indeed reached in some instances.

Semmes surfaces and intrinsic Lipschitz graphs in the Heisenberg group

2018

A Semmes surface in the Heisenberg group is a closed set $S$ that is upper Ahlfors-regular with codimension one and satisfies the following condition, referred to as Condition B. Every ball $B(x,r)$ with $x \in S$ and $0 < r < \operatorname{diam} S$ contains two balls with radii comparable to $r$ which are contained in different connected components of the complement of $S$. Analogous sets in Euclidean spaces were introduced by Semmes in the late $80$'s. We prove that Semmes surfaces in the Heisenberg group are lower Ahlfors-regular with codimension one and have big pieces of intrinsic Lipschitz graphs. In particular, our result applies to the boundary of chord-arc domains and of redu…

The dual equivalence of equations and coequations for automata

2015

The transition structure α : X ? X A of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. We use this algebra-coalgebra duality as a common perspective for the study of equations and coequations. For every automaton ( X , α ) , we define two new automata: free ( X , α ) and cofree ( X , α ) representing, respectively, the greatest set of equations and the smallest set of coequations satisfied by ( X , α ) . Both constructions are shown to be functorial. Our main result is that the restrictions of free and cofree to, respectively, preformations of languages and to quotients A * / C of A * with respect to a congr…

Discrete and Conservative Factorizations in Fib(B)

2021

AbstractWe focus on the transfer of some known orthogonal factorization systems from$$\mathsf {Cat}$$Catto the 2-category$${\mathsf {Fib}}(B)$$Fib(B)of fibrations over a fixed base categoryB: the internal version of thecomprehensive factorization, and the factorization systems given by (sequence of coidentifiers, discrete morphism) and (sequence of coinverters, conservative morphism) respectively. For the class of fibrewise opfibrations in$${\mathsf {Fib}}(B)$$Fib(B), the construction of the latter two simplify to a single coidentifier (respectively coinverter) followed by an internal discrete opfibration (resp. fibrewise opfibration in groupoids). We show how these results follow from thei…

Area minimizing projective planes on the projective space of dimension 3 with the Berger metric

2016

Abstract We show that, among the projective planes embedded into the real projective space R P 3 endowed with the Berger metric, those of least area are exactly the ones obtained by projection of the equatorial spheres of S 3 . This result generalizes a classical result for the projective spaces with the standard metric.