%% Template for writing an abstract for the Oberwolfach Reports
%% maintained by
%% Before submitting the report to the reporter
%% you can run automated tests for common errors online at:
%% https://www.mfo.de/scientific-program/publications/owr/diagnostics
%% The required "owrart.cls" file can be found at
%% https://www.mfo.de/scientific-program/publications/owr/owrart.cls
\documentclass{owrart}
%% Enter additionally required packages below this comment.
%% * Please be conservative and only require common packages.
%% * Do not use any packages, which alter the page/font layout.
%% * For the inclusion of graphics, use the graphicx package.
%% * Please use .eps graphics only (no .jpg, .png or .pdf).
%% Note that the tex source has to be compilable to .dvi format.
% \usepackage{graphicx}
\usepackage{url}
\usepackage{hyperref}
%\newcommand\href[2]{#2}
%\newtheorem{question}{Question}
\newtheorem*{onequestion}{Question}
\theoremstyle{definition}
\newtheorem{problem}{PROBLEM}
%% Enter own definitions (such as \newcommands and custom environments) here.
%% * Please try to avoid using "\def" or "\renewcommand" as they may cause
%% interference among contributions of other authors.
%% * For the same reason, only define commands you really need for your abstract.
\begin{document}
%% --------------------------------------------------------------------------
%% Please use the environment "talk" for each abstract.
%% It has three obligatory and one optional argument. The syntax is:
%% -----------------------
%% \begin{talk}[coauthors]{Name of the speaker}{Title of the talk}{Author Sorting Index}
%% .....
%% \end{talk}
%% -----------------------
%% The names of coauthors will appear in form of "(joint work with ...)"
%%
%% The Author Sorting Index should be given as the last and first name of the speaker,
%% separated by a comma. If for example the name of the speaker is "John Smith", then
%% the correct Author Sorting Index is "Smith, John".
%% Any special characters (like accents, German umlaute, etc.) should be replaced by
%% their "non-special" version, eg replace \"a by a, \'a by a, etc.
%%
%% Please use the standard thebibliography environment to include
%% your references, and try to use labels for the bibitems, which
%% are uniquely assigned to you in order to avoid conflicts with other authors.
%% You can achieve unique labels by using our on initials before every label.
%% -------------------------------------------------------------------------------
\begin{talk}{Collected by G\"unter Rote}
{Open Problems in Discrete Geometry%
%\break {DRAFT}, \today,
%{\count0=\time\divide\count0 by 60 \count2=\count0\multiply \count2 by-60
%\advance\count2 by\time \the\count0:\ifnum\count2<10 0\fi\the\count2}
%\break From the Oberwolfach Workshop, September 2020
%\break {UPDATE}, \today,
}{Rote, Guzzzznter}
\makeatletter
\def\@bibtitlestyle{\par\smallskip}
\makeatother
%1
\begin{problem}[Karim Adiprasito]
\textsc{Repeated halving of simplices}
\par\par\smallskip\noindent
Start with a
$d$-dimensional simplex.
Subdivide the longest edge and cut the simplex into
two simplices of half the area.
Repeat the process recursively with both halves ad infinitum. (The
result is in general not a face-to-face decomposition.)
We assume that the starting simplex is sufficiently
generic, so that there is never a tie in choosing the longest edge.
In dimensions 2 and 3, this process stabilizes after finitely many
iterations in the sense that every new simplex is homothetic to one of
the simplices that have already been seen.
In dimension 4, this is true provided that one starts with a suitable
starting simplex: a generically perturbed orthoscheme.
%\setcounter{question}{0}
\begin{onequestion}
Does this stabilizing behavior occur for any starting simplex, in any dimension?
Or,
on the contrary, can this process lead to arbitrarily
badly shaped simplices, where the ratio between the inradius and the
circumradius approaches $0$?
\end{onequestion}
The question has applications in scientific computing.
\end{problem}
%2
\begin{problem}[Gil Kalai]
\textsc{Complicated intersections} %what?}
\par\smallskip\noindent
Consider a fixed real algebraic variety $N$ in $\mathbb R^d$, and real algebraic
varieties $M$ of a certain type.
We are looking for general statement of the form: If all
intersections between $M$ and affine transformations of $N$ are
``complicated'' then the dimension of the affine hull of $M$ is ``small''.
The model statement for this is the Sylvester--Gallai Theorem: Here,
$M$ is a set of points and $N$ is a line. If all nontrivial
intersections have more then 2 points, then the affine hull of $M$
has dimension 1.
\end{problem}
%3
\begin{problem}[Tomasz Szemberg]
\textsc{Absolute linear Harbourne constants}
\par\smallskip\noindent
Harbourne constants have been introduced
in connection with the Bounded Negativity Conjecture
in algebraic geometry~\cite{BNCarrangements15}. However, they can be considered purely combinatorially.
Let $\mathbb K$ be a field and
$\mathcal{L}$ %=\left\{L_1,\ldots,L_d\right\}$ be a finite set
be a set of
$d$ lines in the projective plane
$\mathbb{P}^2(\mathbb{K})$. Let
$%\mathcal{P}=
\left\{P_1,\ldots,P_s\right\}$ be the set of points
where at least two lines of $\mathcal{L}$ intersect, and let
$m_i$ be the number of lines passing through $P_i$.
The rational number
$$H(\mathbb{K},\mathcal{L})=\frac{d^2-\sum_{i=1}^sm_i^2}{s}$$
is the Herbourne constant of the arrangement $\mathcal{L}$.
Taking the minimum over all arrangements of $d$ lines in $\mathbb{P}^2(\mathbb{K})$,
we obtain the linear Harbourne constant of $d$ lines over $\mathbb{K}$
$$H(\mathbb{K},d)=\min_{|\mathcal{L}|=d}H(\mathbb{K},\mathcal{L}).$$
Finally, taking the minimum over all fields $\mathbb{K}$ we arrive at the absolute linear Harbourne constant of $d$ lines
$$H(d)=\min_{\mathbb{K}}H(\mathbb{K},d).$$
\begin{onequestion}
Compute the numbers $H(d)$.
\end{onequestion}
This has been done for $1\leq d\leq 31$ and for $d$ of the form $d=q^2+q+1$~\cite{DHS}. The article contains also a conjectural
formula for these numbers.
\begin{thebibliography}{1}
\bibitem{BNCarrangements15}
T.~Bauer, S.~Di~Rocco, B.~Harbourne, J.~Huizenga, A.~Lundman, P.~Pokora, and
T.~Szemberg,
\newblock \textit{Bounded negativity and arrangements of lines},
\newblock {Int. Math. Res. Not. IMRN} \textbf{19} (2015), 9456--9471.
\bibitem{DHS}
M.~Dumnicki, D.~Harrer, and J.~Szpond,
\newblock \textit{On absolute linear {H}arbourne constants},
\newblock Finite Fields Appl. \textbf{51} (2018), 371--387.
\end{thebibliography}
\end{problem}
%4
\begin{problem}[Tomasz Szemberg]
\textsc{Projective plane of order 10}
\par\smallskip\noindent
A computer proof of the non-existence of a projective plane of order
$10$
was announced in 1989~\cite{Lam}.
% With colleagues in Krakau we tried to reconstruct the proof, however
% we
% failed. I am seeking for a person who could explain Lam's proof to the
% extent that the computer proof of his group can be verified. Strangely
% enough, it seems that nobody repeated their computations. It would be
% impossible in experimental sciences to claim a result without independent
% verification :)
Has this proof ever been independently verified?
\emph{Note.} (Konrad Swanepoel) It seems that
the non-existence of a
projective plane of order 10 was independently checked as
described in a M.Sc.\ thesis from 2010~\cite{roy}.
There are other
verifications of parts of the search~\cite{perrott}.
Curtis Bright
and coworkers are busy using SAT solvers to produce more
rigorous
computer-based proofs, see
\url{https://cs.uwaterloo.ca/~cbright/#writings}.
%\break
There is no complete formal proof yet, but it looks % to me
as if this
is not very far away. The most enlightening of his papers is
\cite{curtis}.
\begin{thebibliography}{9}
\bibitem{Lam}
C. W. H. Lam,
L. Thiel and S. Swiercz,
\textit{The
nonexistence of finite projective planes of order~10}. Canad. J. Math.
\textbf{41} (1989),
\href{https://doi.org/10.4153/CJM-1989-049-4}{1117--1123}.
\bibitem{perrott}
X. Perrott, \emph{Existence of
projective planes},
arXiv:\href{http://arxiv.org/abs/1603.05333}{1603.05333}, (2016).
\bibitem{roy} D. J. Roy, \textit{Confirmation of the
non-existence of a projective plane of order 10}, Masterâ€™s
dissertation, Carleton University, 2010.
\bibitem{curtis}
C. Bright,
\textit{A SAT-based Resolution of Lam's Problem}, % Preprint,
\url{https://cs.uwaterloo.ca/~cbright/reports/lams-preprint.pdf},
September 2020.
\end{thebibliography}
\end{problem}
%5
\begin{problem}[Luis Montejano]
\textsc{Sections that are bodies of revolution}
\par\smallskip\noindent
If all hyperplane sections of a convex body of dimension at least 4
are either single points or bodies of revolution, prove that the
body is itself a body of revolution.
\end{problem}
%6
\begin{problem}[Gil Kalai]
\textsc{4-polytopes with dense graphs}
\par\smallskip\noindent
Suppose a simplicial 4-polytope $P$ with $n$ vertices has the
property that, among every three vertices, at least two of them
are joined by an edge. Does it follow that the graph of $P$
contains a ``large'' complete subgraph, say, of size $n/10$?
\end{problem}
%7
\begin{problem}[Arseniy Akopyan]
\textsc{\\Unbalanced ham-sandwich cuts for spherical caps}
\par\smallskip\noindent
We are given two continuous probability measures on the 2-dimensional
sphere %$S^2$
and a parameter $0<\alpha<1/2$. Is there always a spherical
cap (intersection with a half-space) that has measure $\alpha$ for
both measures?
\end{problem}
%8
\begin{problem}[Raphael Steiner]
\textsc{\\Bichromatic triangles in arrangements of pseudolines}
\par\smallskip\noindent
A pseudoline is a non-self-intersecting infinite curve in
$\mathbb{R}^2$ dividing the plane into two connected components. A
\emph{simple} arrangement of pseudolines is a set of pseudolines
such that any two distinct pseudolines intersect in a point, and
no point is contained in three or more pseudolines.
% The following question was raised in
\begin{onequestion}
%Suppose $\mathcal{A}$ is
In a simple arrangement of red and blue pseudolines,
%equipped with
%a red-blue-coloring of the pseudolines such that each color appears
%at least once.
is there always a bounded triangular face % of the arrangement
that is incident to a red and a blue pseudoline?
% whose three bounding pseudolines do not all have the same color?
% \cite{ai}
\end{onequestion}
It is easy to see that this is true for planar \emph{line} arrangements.
It holds also for the more general class of
% The authors of \cite{ai} showed that the above question has a positive
% answer if $\mathcal{A}$ is an arrangement of
\emph{approaching} pseudoline
% which includes all planar line
arrangements~\cite{ai}.
%The problem remains open in general.
\begin{thebibliography}1
\bibitem{ai} Stefan Felsner, Alexander Pilz, and Patrick Schnider,
\textit{Arrangements of approaching
pseudo-lines}. arXiv:\href{http://arxiv.org/abs/2001.08419}{2001.08419}, (2020).
\end{thebibliography}
\end{problem}
%9
\begin{problem}[Bal\'azs Keszegh]
\textsc{Hereditary polychromatic $k$-colorings}
\par\smallskip\noindent For a hypergraph $\mathcal H$ denote by $m_k$ the smallest number for
which we can $k$-color the vertices such that on every hyperedge of
size at least $m_k$, all $k$ colors appear. Denote by $m^*_k$ the
maximum of $m_k$ over every induced subhypergraph of $\mathcal H$.
Berge showed that if for a hypergraph $m^*_2=2$ then $m^*_k=k$
for all $k$. What about larger $m^*_2$? Does $m^*_2=3$ imply that
$m^*_3$ is finite?
\end{problem}
%10
\begin{problem}[Emo Welzl]
\textsc{Minimum
number of partial triangulations}
\par\smallskip\noindent
A partial triangulation of a set of $n$ points in the plane is a triangulation
of the convex hull that may use the interior points as vertices, but does not
have to use all of them.
\begin{onequestion}
What is the smallest number of partial triangulations that a set
of
$n$ points in general position can have?
Is it the Catalan number $C_{n-2}=\frac 1{n-1}\binom{2n-4}{n-2}$?
%, the $(n-2)^{\text{nd}}$
\end{onequestion}
For full triangulations, where all interior points have to be used,
smallest known number of full triangulations,
roughly $\sqrt{12}^n$,
is obtained by
the so-called \emph{double circle}, which is constructed by putting an interior point near
the midpoint of every edge of a regular $\frac n2$-gon.
By contrast, $n$ points in convex position have
$C_{n-2}\sim 4^n$ full (or equivalently, partial) triangulations.
Interestingly, the double circle has {exactly}
the same number $C_{n-2}%\sim 4^n
$ of partial triangulations.
% Francisco Santos and Raimund Seidel. A better upper bound on the
% number of triangulations of a planar point set. J. Comb. Theory,
% Ser. A, 102(1):186--193, 2003.
\end{problem}
%11
\begin{problem}[Karim Adiprasito]
\textsc{\\The compact part of a polyhedral subdivision}
\par\smallskip\noindent
Take a polyhedral subdivision of $\mathbb R^3$ into finitely many
parts, none of which contains a line, and look at the union of all
bounded faces. This set is contractible.
Is it collapsible?
\end{problem}
%12
\begin{problem}[Stefan Langerman]
\textsc{\\The centerpoint constant for complete intersections}
\par\smallskip\noindent
For every set of $n$ lines in the plane, there is a point $p$ such
that for
every halfspace $H$ containing $p$ there is a subset of at least
$\sqrt{n/3}$ of lines all of whose intersections lie in $H$.
There are examples that show that the bound cannot be improved
to more than
$\sqrt{n}$. What is the right constant?
\end{problem}
%13
\begin{problem}[Gil Kalai]
\textsc{Sets consisting of two convex pieces}
\par\smallskip\noindent
Suppose there is a family of sets in $d$ dimensions, each
of which is the disjoint union of two nonempty closed convex sets.
Moreover, the intersection of any $2,3,\ldots$ or $d+1$ sets from the
family
has the same property of consisting of exactly two %disjoint
convex pieces. Does it follow that the whole family has a
nonempty intersection?
Micha Perles constructed an example that shows that the statement is
not true in the plane if the number ``two'' of convex pieces is replaced by 48.
\end{problem}
%14
\begin{problem}[Michael Dobbins]
\textsc{Extending piecewise-linear maps from the boundary
to the interior in a continuous manner}
\par\smallskip\noindent
Take a fixed reference triangle $ABC$,
and consider a piecewise-linear (PL) one-to-one map from the boundary of the
triangle $ABC$ into the plane (in other words, a PL parameterization
of a simple polygon).
Such a map can be easily extended to a
PL one-to-one map from whole
triangular area $ABC$ %, including the interior,
into the plane.
Can this be done in a way that depends continuously on the boundary
map? In other words, is there a continuous function that assigns to
every %from the space of
PL one-to-one map $\partial ABC\to \mathbb R^2$
%to the space of
a PL one-to-one map $ ABC\to \mathbb R^2$ extending it?
\end{problem}
\end{talk}
\end{document}
\begin{thebibliography}{99}
\bibitem{JS_Mu90}
M.~Muster, \textit{Computing certain invariants of topological
spaces of dimension three}, Topology \textbf{32} (1990), 100--120.
\bibitem{JS_Mu90a}
M.~Muster, \textit{Computing other invariants of topological spaces
of dimension three}, Topology \textbf{32} (1990), 120--140.
\end{thebibliography}