Source author record

Michal Adamaszek

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.AT Computational Complexity math.AG math.CT math.GT math.MG

Catalog footprint

Research overview

16works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2018arXiv

Metric reconstruction via optimal transport

Given a sample of points $X$ in a metric space $M$ and a scale $r>0$ , the Vietoris-Rips simplicial complex $\mathrm{VR}(X;r)$ is a standard construction to attempt to recover $M$ from $X$ up to homotopy type. A deficiency of this approach is that $\mathrm{VR}(X;r)$ is not metrizable if it is not locally finite, and thus does not recover metric information about $M$ . We attempt to remedy this shortcoming by defining a metric space thickening of $X$ , which we call the \emph{Vietoris-Rips thickening} $\mathrm{VR}^m(X;r)$ , via the theory of optimal transport. When $M$ is a complete Riemannian manifold, or alternatively a compact Hadamard space, we show that the the Vietoris-Rips thickening satisfies Hausmann's theorem ( $\mathrm{VR}^m(M;r)\simeq M$ for $r$ sufficiently small) with a simpler proof: homotopy equivalence $\mathrm{VR}^m(M;r)\to M$ is canonically defined as a center of mass map, and its homotopy inverse is the (now continuous) inclusion map $M\hookrightarrow\mathrm{VR}^m(M;r)$ . Furthermore, we describe the homotopy type of the Vietoris-Rips thickening of the $n$ -sphere at the first positive scale parameter $r$ where the homotopy type changes.

preprint2015arXiv

A note on independence complexes of chordal graphs and dismantling

We show that the independence complex of a chordal graph is contractible if and only if this complex is dismantlable (strong collapsible) and it is homotopy equivalent to a sphere if and only if its core is a cross-polytopal sphere. The proof uses the properties of tree models of chordal graphs.

preprint2015arXiv

Face numbers of down-sets

We compare various viewpoints on down-sets (simplicial complexes), illustrating how the combinatorial inclusion-exclusion principle may serve as an alternative to more advanced methods of studying their face numbers.

preprint2014arXiv

Transitivity is not a (big) restriction on homotopy types

For every simplicial complex K there exists a vertex-transitive simplicial complex homotopy equivalent to a wedge of copies of K with some copies of the circle. It follows that every simplicial complex can occur as a homotopy wedge summand in some vertex-transitive complex. One can even demand that the vertex-transitive complex is the clique complex of a Cayley graph or that it is facet-transitive.

preprint2013arXiv

An upper bound theorem for a class of flag weak pseudomanifolds

If K is an odd-dimensional flag closed manifold, flag generalized homology sphere or a more general flag weak pseudomanifold with sufficiently many vertices, then the maximal number of edges in K is achieved by the balanced join of cycles. The proof relies on stability results from extremal graph theory. In the case of manifolds we also offer an alternative (very) short proof utilizing the non-embeddability theorem of Flores. The main theorem can also be interpreted without the topological contents as a graph-theoretic extremal result about a class of graphs such that 1) every maximal clique in the graph has size d+1 and 2) every clique of size d belongs to exactly two maximal cliques.

preprint2013arXiv

Extremal problems related to Betti numbers of flag complexes

We study the problem of maximizing Betti numbers of simplicial complexes. We prove an upper bound of 1.32^n for the sum of Betti numbers of any n-vertex flag complex and 1.25^n for the independence complex of a triangle-free graph. These findings imply upper bounds for the Betti numbers of various related classes of spaces, including the neighbourhood complex of a graph. We also make some related observations.

preprint2013arXiv

The smallest nonevasive graph property

A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form "is there an edge between vertices u and v" requires, in the worst case, to ask about all pairs of vertices. Most "natural" graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n=6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that it is essentially the unique such with n at most 5.

preprint2012arXiv

Clique complexes and graph powers

We study the behaviour of clique complexes of graphs under the operation of taking graph powers. As an example we compute the clique complexes of powers of cycles, or, in other words, the independence complexes of circular complete graphs.

preprint2012arXiv

Hard squares on cylinders revisited

We consider the independence complexes of square grids with cylindrical boundary conditions. When one of the dimensions is small we use simple reductions induced by edge removals to show explicit natural homotopy equivalences between those spaces. In the second part we expand the results of Jonsson, who calculated the Euler characteristic of cylinders with odd circumference. We describe a series of results for cylinders of even circumference. Finally we define a completely independent combinatorial model (necklaces) which calculates the generating functions of the Euler characteristic of cylindrical grids. We conjecture that this model has some particularly simple structure.

preprint2012arXiv

Small flag complexes with torsion

We classify flag complexes on at most 12 vertices with torsion in the first homology group. The result is moderately computer-aided. As a consequence we confirm a folklore conjecture that the smallest poset whose order complex is homotopy equivalent to the real projective plane (and also the smallest poset with torsion in the first homology group) has exactly 13 elements.

preprint2012arXiv

Special cycles in independence complexes and superfrustration in some lattices

We prove that the independence complexes of some grids have exponential Betti numbers. This corresponds to the number of ground states in the hard-core model in statistical physics with fermions in the vertices of the grid.

preprint2012arXiv

Splittings of independence complexes and the powers of cycles

We use two cofibre sequences to identify some combinatorial situations when the independence complex of a graph splits into a wedge sum of smaller independence complexes. Our main application is to give a recursive relation for the homotopy types of the independence complexes of powers of cycles, which answers an open question of D. Kozlov.

preprint2011arXiv

The Symmetric Join Operad

The join operad arises from the combinatorial study of the iterated join of simplices. We study a suitable simplicial version of this operad which includes the symmetries given by permutations of the factors of the join. From this combinatorics we construct an E-infinity operad which coacts naturally on the chains of a simplicial set.

preprint2011arXiv

Vertex decompositions of two-dimensional complexes and graphs

We investigate families of two-dimensional simplicial complexes defined in terms of vertex decompositions. They include nonevasive complexes, strongly collapsible complexes of Barmak and Miniam and analogues of 2-trees of Harary and Palmer. We investigate the complexity of recognition problems for those families and some of their combinatorial properties. Certain results follow from analogous decomposition techniques for graphs. For example, we prove that it is NP-complete to decide if a graph can be reduced to a discrete graph by a sequence of removals of vertices of degree 3.

preprint2010arXiv

Spaces of algebraic and continuous maps between real algebraic varieties

We consider the inclusion of the space of algebraic (regular) maps between real algebraic varieties in the space of all continuous maps. For a certain class of real algebraic varieties, which include real projective spaces, it is well known that the space of real algebraic maps is a dense subset of the space of all continuous maps. Our first result shows that, for this class of varieties, the inclusion is also a homotopy equivalence. After proving this, we restrict the class of varieties to real projective spaces. In this case, the space of algebraic maps has a ` minimum degree\rq filtration by finite dimensional subspaces and it is natural to expect that the homotopy types of the terms of the filtration approximate closer and closer the homotopy type of the space of continuous mappings as the degree increases. We prove this and compute the lower bounds of this approximation for ` even\rq components of these spaces (more precisely, we prove a very similar and closely related result, and state this one as a conjecture).

preprint2008arXiv

Combinatorics of the change-making problem

We investigate the structure of the currencies (systems of coins) for which the greedy change-making algorithm always finds an optimal solution (that is, a one with minimum number of coins). We present a series of necessary conditions that must be satisfied by the values of coins in such systems. We also uncover some relations between such currencies and their sub-currencies.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Michal Adamaszek

Research overview

Is this your work?

16 publications

Metric reconstruction via optimal transport

A note on independence complexes of chordal graphs and dismantling

Face numbers of down-sets

Transitivity is not a (big) restriction on homotopy types

An upper bound theorem for a class of flag weak pseudomanifolds

Extremal problems related to Betti numbers of flag complexes

The smallest nonevasive graph property

Clique complexes and graph powers

Hard squares on cylinders revisited

Small flag complexes with torsion

Special cycles in independence complexes and superfrustration in some lattices

Splittings of independence complexes and the powers of cycles

The Symmetric Join Operad

Vertex decompositions of two-dimensional complexes and graphs

Spaces of algebraic and continuous maps between real algebraic varieties

Combinatorics of the change-making problem

See the researcher in context

Building this map preview