Source author record

May Szedlák

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

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Discrete Mathematics math.CO math.OC math.SP

Catalog footprint

Research overview

2works

6topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Higher Dimensional Discrete Cheeger Inequalities

For graphs there exists a strong connection between spectral and combinatorial expansion properties. This is expressed, e.g., by the discrete Cheeger inequality, the lower bound of which states that $λ(G) \leq h(G)$ , where $λ(G)$ is the second smallest eigenvalue of the Laplacian of a graph $G$ and $h(G)$ is the Cheeger constant measuring the edge expansion of $G$ . We are interested in generalizations of expansion properties to finite simplicial complexes of higher dimension (or uniform hypergraphs). Whereas higher dimensional Laplacians were introduced already in 1945 by Eckmann, the generalization of edge expansion to simplicial complexes is not straightforward. Recently, a topologically motivated notion analogous to edge expansion that is based on $\mathbb{Z}_2$ -cohomology was introduced by Gromov and independently by Linial, Meshulam and Wallach. It is known that for this generalization there is no higher dimensional analogue of the lower bound of the Cheeger inequality. A different, combinatorially motivated generalization of the Cheeger constant, denoted by $h(X)$ , was studied by Parzanchevski, Rosenthal and Tessler. They showed that indeed $λ(X) \leq h(X)$ , where $λ(X)$ is the smallest non-trivial eigenvalue of the ( $(k-1)$ -dimensional upper) Laplacian, for the case of $k$ -dimensional simplicial complexes $X$ with complete $(k-1)$ -skeleton. Whether this inequality also holds for $k$ -dimensional complexes with non-complete $(k-1)$ -skeleton has been an open question. We give two proofs of the inequality for arbitrary complexes. The proofs differ strongly in the methods and structures employed, and each allows for a different kind of additional strengthening of the original result.

preprint2014arXiv

Combinatorial Redundancy Detection

The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by $n$ equality constraints in $n+d$ variables, where the variables are constrained to be nonnegative. A variable $x_r$ is called redundant, if after removing $x_r \geq 0$ the LP still has the same feasible region. The time needed to solve such an LP is denoted by $LP(n,d)$ . It is easy to see that solving $n+d$ LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves $n+d$ linear programs, but each of them has at most $s$ variables, where $s$ is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover - and this is the combinatorial aspect - it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable $x_r$ one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for $x_r$ . In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time $\mathcal{O}(d \cdot (n+d) \cdot s^{d-1} \cdot LP(s,d) + d \cdot s^{d} \cdot LP(n,d))$ to detect all redundancies. In the case where all constraints are in general position, the running time is $\mathcal{O}(s \cdot LP(n,d) + (n+d) \cdot LP(s,d))$ , which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements.

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.