Source author record

Winfried Hochstättler

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-ph math.MP

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Colorings of oriented planar graphs avoiding a monochromatic subgraph

For a fixed simple digraph $F$ and a given simple digraph $D$ , an $F$ -free $k$ -coloring of $D$ is a vertex-coloring in which no induced copy of $F$ in $D$ is monochromatic. We study the complexity of deciding for fixed $F$ and $k$ whether a given simple digraph admits an $F$ -free $k$ -coloring. Our main focus is on the restriction of the problem to planar input digraphs, where it is only interesting to study the cases $k \in \{2,3\}$ . From known results it follows that for every fixed digraph $F$ whose underlying graph is not a forest, every planar digraph $D$ admits an $F$ -free $2$ -coloring, and that for every fixed digraph $F$ with $Δ(F) \ge 3$ , every oriented planar graph $D$ admits an $F$ -free $3$ -coloring. We show in contrast, that - if $F$ is an orientation of a path of length at least $2$ , then it is NP-hard to decide whether an acyclic and planar input digraph $D$ admits an $F$ -free $2$ -coloring. - if $F$ is an orientation of a path of length at least $1$ , then it is NP-hard to decide whether an acyclic and planar input digraph $D$ admits an $F$ -free $3$ -coloring.

preprint2022arXiv

Kirchberger's Theorem for Complexes of Oriented Matroids

The separation theorem of Kirchberger can be proven using a combination of Farkas' Lemma and Caratheodory's Theorem. Since those theorems are at the heart of oriented matroids, we are interested in a generalization of Kirchberger's Theorem to them. This has already been done for rank 3 oriented matroids. Here we prove it for complexes of oriented matroids, which are a generalization of oriented matroids.

preprint2022arXiv

The Chromatic Polynomial of a Digraph

An acyclic coloring of a digraph as defined by Neumann-Lara is a vertex-coloring such that no monochromatic directed cycles occur. Counting the number of such colorings with $k$ colors can be done by counting so-called Neumann-Lara-coflows (NL-coflows), which build a polynomial in $k$ . We will present a representation of this polynomial using totally cyclic subdigraphs, which form a graded poset $Q$ . Furthermore we will decompose our NL-coflow polynomial, which becomes the chromatic polynomial of a digraph by multiplication with the number of colors to the number of components, examining the special structure of the poset of totally cyclic subdigraphs with fixed underlying undirected graph. This decomposition will confirm the equality of our chromatic polynomial of a digraph and the chromatic polynomial of the underlying undirected graph in the case of symmetric digraphs.

preprint2021arXiv

Independent Hyperplanes in Oriented Paving Matroids

In 1993, Csima and Sawyer proved that in a non-pencil arrangement of n pseudolines, there are at least $\frac{6}{13}n$ simple points of intersection. Since pseudoline arrangements are the topological representations of reorientation classes of oriented matroids of rank $3$ , in this paper, we will use this result to prove by induction that an oriented paving matroid of rank $r \ge 3$ on $n$ elements, where $n \geq 5+ r$ , has at least $\frac{12}{13(r-1)} \binom{n}{r-2}$ independent hyperplanes, yielding a new necessary condition for a paving matroid to be orientable.

preprint2014arXiv

Semicircle law for a matrix ensemble with dependent entries

We study ensembles of random symmetric matrices whose entries exhibit certain correlations. Examples are distributions of Curie-Weiss-type. We provide a criterion on the correlations ensuring the validity of Wigner's semicircle law for the eigenvalue distribution measure. In case of Curie-Weiss distributions this criterion applies above the critical temperature (i.e. $β<1$ ). We also investigate the largest eigenvalue of certain ensembles of Curie-Weiss type and find a transition in its behavior at the critical temperature.

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.

Winfried Hochstättler

Research overview

Is this your work?

5 publications

Colorings of oriented planar graphs avoiding a monochromatic subgraph

Kirchberger's Theorem for Complexes of Oriented Matroids

The Chromatic Polynomial of a Digraph

Independent Hyperplanes in Oriented Paving Matroids

Semicircle law for a matrix ensemble with dependent entries

See the researcher in context

Building this map preview