Search results for "combinatoric"
showing 10 items of 1776 documents
Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
2006
A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infi…
A combinatorial view on string attractors
2021
Abstract The notion of string attractor has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-based compressors. A string attractor for a word w = w 1 w 2 ⋯ w n is a subset Γ of the positions { 1 , … , n } , such that all distinct factors of w have an occurrence crossing at least one of the elements of Γ. In this paper we explore the notion of string attractor by focusing on its combinatorial properties. In particular, we show how the size of the smallest string attractor of a word varies when combinatorial operations are applied and we deduce that such a measure is not monotone. Moreover, we introduce a c…
F-signature of pairs: Continuity, p-fractals and minimal log discrepancies
2011
This paper contains a number of observations on the {$F$-signature} of triples $(R,\Delta,\ba^t)$ introduced in our previous joint work. We first show that the $F$-signature $s(R,\Delta,\ba^t)$ is continuous as a function of $t$, and for principal ideals $\ba$ even convex. We then further deduce, for fixed $t$, that the $F$-signature is lower semi-continuous as a function on $\Spec R$ when $R$ is regular and $\ba$ is principal. We also point out the close relationship of the signature function in this setting to the works of Monsky and Teixeira on Hilbert-Kunz multiplicity and $p$-fractals. Finally, we conclude by showing that the minimal log discrepancy of an arbitrary triple $(R,\Delta,\b…
Classifying G-graded algebras of exponent two
2019
Let F be a field of characteristic zero and let $$\mathcal{V}$$ be a variety of associative F-algebras graded by a finite abelian group G. If $$\mathcal{V}$$ satisfies an ordinary non-trivial identity, then the sequence $$c_n^G(\mathcal{V})$$ of G-codimensions is exponentially bounded. In [2, 3, 8], the authors captured such exponential growth by proving that the limit $$^G(\mathcal{V}) = {\rm{lim}}_{n \to \infty} \sqrt[n]{{c_n^G(\mathcal{V})}}$$ exists and it is an integer, called the G-exponent of $$\mathcal{V}$$ . The purpose of this paper is to characterize the varieties of G-graded algebras of exponent greater than 2. As a consequence, we find a characterization for the varieties with …
Plenty of big projections imply big pieces of Lipschitz graphs
2020
I prove that a closed $n$-regular set $E \subset \mathbb{R}^{d}$ with plenty of big projections has big pieces of Lipschitz graphs. This answers a question of David and Semmes.
Reciprocal lower bound on modulus of curve families in metric surfaces
2019
We prove that any metric space $X$ homeomorphic to $\mathbb{R}^2$ with locally finite Hausdorff 2-measure satisfies a reciprocal lower bound on modulus of curve families associated to a quadrilateral. More precisely, let $Q \subset X$ be a topological quadrilateral with boundary edges (in cyclic order) denoted by $\zeta_1, \zeta_2, \zeta_3, \zeta_4$ and let $\Gamma(\zeta_i, \zeta_j; Q)$ denote the family of curves in $Q$ connecting $\zeta_i$ and $\zeta_j$; then $\text{mod} \Gamma(\zeta_1, \zeta_3; Q) \text{mod} \Gamma(\zeta_2, \zeta_4; Q) \geq 1/\kappa$ for $\kappa = 2000^2\cdot (4/\pi)^2$. This answers a question concerning minimal hypotheses under which a metric space admits a quasiconfor…
Accessible parts of boundary for simply connected domains
2018
For a bounded simply connected domain $\Omega\subset\mathbb{R}^2$, any point $z\in\Omega$ and any $0<\alpha<1$, we give a lower bound for the $\alpha$-dimensional Hausdorff content of the set of points in the boundary of $\Omega$ which can be joined to $z$ by a John curve with a suitable John constant depending only on $\alpha$, in terms of the distance of $z$ to $\partial\Omega$. In fact this set in the boundary contains the intersection $\partial\Omega_z\cap\partial\Omega$ of the boundary of a John sub-domain $\Omega_z$ of $\Omega$, centered at $z$, with the boundary of $\Omega$. This may be understood as a quantitative version of a result of Makarov. This estimate is then applied to obta…
SURFACE SUBGROUPS OF RIGHT-ANGLED ARTIN GROUPS
2007
We consider the question of which right-angled Artin groups contain closed hyperbolic surface subgroups. It is known that a right-angled Artin group $A(K)$ has such a subgroup if its defining graph $K$ contains an $n$-hole (i.e. an induced cycle of length $n$) with $n\geq 5$. We construct another eight "forbidden" graphs and show that every graph $K$ on $\le 8$ vertices either contains one of our examples, or contains a hole of length $\ge 5$, or has the property that $A(K)$ does not contain hyperbolic closed surface subgroups. We also provide several sufficient conditions for a \RAAG to contain no hyperbolic surface subgroups. We prove that for one of these "forbidden" subgraphs $P_2(6)$, …
Real quadrics in C n , complex manifolds and convex polytopes
2006
In this paper, we investigate the topology of a class of non-Kähler compact complex manifolds generalizing that of Hopf and Calabi-Eckmann manifolds. These manifolds are diffeomorphic to special systems of real quadrics Cn which are invariant with respect to the natural action of the real torus (S1)n onto Cn. The quotient space is a simple convex polytope. The problem reduces thus to the study of the topology of certain real algebraic sets and can be handled using combinatorial results on convex polytopes. We prove that the homology groups of these compact complex manifolds can have arbitrary amount of torsion so that their topology is extremely rich. We also resolve an associated wall-cros…
Weak separation condition, Assouad dimension, and Furstenberg homogeneity
2015
We consider dimensional properties of limit sets of Moran constructions satisfying the finite clustering property. Just to name a few, such limit sets include self-conformal sets satisfying the weak separation condition and certain sub-self-affine sets. In addition to dimension results for the limit set, we manage to express the Assouad dimension of any closed subset of a self-conformal set by means of the Hausdorff dimension. As an interesting consequence of this, we show that a Furstenberg homogeneous self-similar set in the real line satisfies the weak separation condition. We also exhibit a self-similar set which satisfies the open set condition but fails to be Furstenberg homogeneous.