Description
Bence Csajbók (MTA-ELTE Geometric and Algebraic Combinatorics Research Group):
Linear sets of finite projective spaces
Let $V$ be an $r$-dimensional vector space over the finite field $\mathbb{F}_{q^n}$ and let $\Lambda$ denote the projective space $\mathrm{PG}(r-1,q^n)$ defined by the $\mathbb{F}_{q^n}$-subspaces of $V$. For a $k$-dimensional $\mathbb{F}_q$-subspace $U$ of $V$ the linear set of rank $k$ defined by $U$ is the point set
\[L_U:=\{\langle {\bf u}\rangle_{\mathbb{F}_{q^n}} \colon {\bf u} \in U\setminus \{ {\bf 0} \}\}\subseteq \Lambda.\]
Linear sets have been used in the last three decades to construct and to characterize various objects in finite geometry. Their first application was to construct small blocking sets and hence to disprove many related conjectures. I will present results about the following problems regarding linear sets:
What can we say about the $\mathbb{F}_q$-subspaces $U$ and $W$ if the linear sets $L_U$ and $L_W$ coincide? What can we say if they are $\mathrm{P\Gamma L}(r,q^n)$-equivalent?
The maximum size of a linear set $L_U$ of rank $k$ is $(q^k-1)/(q-1)$. If $|L_U|$ obtains this bound, then $k\leq rn/2$ and we call $U$ and $L_U$ \emph{scattered}. If $k=rn/2$ and $|L_U|=(q^{rn/2}-1)/(q-1)$, then $U$ and $L_U$ are called \emph{maximum scattered}. Such linear sets are two intersection sets in $\Lambda$ with respect to hyperplanes, they define two-weight linear codes, strongly regular graphs and for $q=2$ translation caps and small complete caps. How can we find examples? How can we decide whether two examples are equivalent?
For an $\mathbb{F}_q$-subspace $\mathcal C$ of $\mathbb{F}_q^{n\times n}$ the minimum rank distance $d$ of $\mathcal C$ is the minimum rank of the non-zero matrices in $\mathcal C$. It can be shown that $|\mathcal C|\leq q^{n(n-d+1)}$. In case of equality $\mathcal C$ is called an \emph{$\mathbb{F}_q$-linear MRD-code} (the $d=n$ case corresponds to semifields). Left and right idealisers of MRD-codes are defined as $L(\mathcal{C})=\{A\in \mathbb{F}_q^{n\times n} \colon A\mathcal{C} \subseteq \mathcal{C}\}$ and $R(\mathcal{C})=\{A\in \mathbb{F}_q^{n\times n} \colon \mathcal{C}A \subseteq \mathcal{C}\}$ and they are isomorphic to finite fields of size at most $q^n$. We call an $\mathbb{F}_q$-subspace $U$ of $V$ $h$-scattered if $\langle U \rangle_{\mathbb{F}_{q^n}}=V$ and the $h$-dimensional $\mathbb{F}_{q^n}$-subspaces of $V$ meet $U$ in $\mathbb{F}_q$-subspaces of dimension at most $h$ (note that $U$ is $1$-scattered if and only if it is scattered and $\langle U \rangle_{q^n}=V$). An MRD-code with at least one idealiser isomorphic to $\mathbb{F}_{q^n}$ corresponds to an $n$-dimensional $(n-d)$-scattered $\mathbb{F}_q$-subspace in an $(n-d+1)$-dimensional $\mathbb{F}_{q^n}$-space (so if $d=n-1$, then to a maximum scattered subspace). What can we say about MRD-codes with both idealisers isomorphic to $\mathbb{F}_{q^n}$? What is the maximum dimension of an $h$-scattered subspace and what can we say about the extremal examples?
Zoltán Lóránt Nagy (MTA-ELTE Geometric and Algebraic Combinatorics Research Group):
Some results in extremal combinatorics
In my Bolyai Research plan, I put the focus on the interplay between geometrical motivation for extremal combinatorial questions, and methods from algebra or probability theory.
In this short talk, I will select three recent results to present. The first one is related to an old problem of Erdős, where one has to explore the distribution of certain measures (like distances) determined by geometrical objects. While these are strongly connected to extremal graph theory of Turán-type problems, our results relies on algebraic reformulation and deep polynomial methods, beside combinatorial tools.
The second one concerns a special case of the generalization of the well known Turán theorem, namely a certain so-called supersaturation result. Here the upper bounds are coming from finite geometric arguments and finite field type constructions.
Finally, the last result solves partially a more than 50 years old conjecture of Erdős, which states that any graph on $n$ vertices which does not contain a fixed $r$-degenerate bipartite graph $F$ has at most $Cn^{2-1/r}$ edges, where $C$ is a constant depending only on $F$. Our proof uses supersaturation and random walks on an auxiliary graph.
Petra Csomós (ELTE, Dept. of Applied Analysis and Computational Mathematics):
Innovative time integrators and their application
Predicting the future state of a system defined by time-dependent
processes is based on the numerical solution of mathematical models.
Since these models are usually complicated differential equations or
their systems, their exact solution is unknown, so a numerical
approximation is needed. We consider the numerical solution to be
satisfactory only if it is convergent and stable.
The talk gives an insight to the derivation and to important properties
of innovative time integrators (operator splitting procedures,
exponential and Magnus-type integrators). We briefly introduce how their
convergence can be studied in a functional analytic framework, i.e. by
using operator semigroup theory. We show our latest result concerning
the second-order convergence of a Magnus-type integrator when applied to
semilinear abstract delay equations. As an example we consider an
epidemic model and illustrate our theoretical results by numerical
experiments.
Tamás Héger (MTA-ELTE Geometric and Algebraic Combinatorics Research Group):
Combinatorial problems in finite geometries
There are a couple of graph theoretical problems in which finite geometric constructions play an important role; the incidence graphs of projective planes are extremal examples in the Zarankiewicz problem and in the cage problem as well, for instance. Also, there are several graph theoretical notions which, when implemented in a finite geometrical setting, lead to interesting questions in finite geometries; metric dimension, dominating sets and upper chromatic number are just three to name. In the talk I mostly, but not only, present studies about finite projective planes and their substructures related to graph theoretic questions.
Szünet
Kristóf Bérczi (MTA-ELTE Egerváry Research Group on Combinatorial Optimization): Improving the integrality gap for multiway cut
In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of $k$ terminal nodes, and the goal is to partition the node set of the graph into $k$ non-empty parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for $k\ge 3$ is APX-hard.
For arbitrary $k$, the best-known approximation factor is $1.2965$ due to Sharma and Vondr\'{a}k while the best known inapproximability factor is $1.2$ due to Angelidakis, Makarychev and Manurangsi. In this talk, we improve on the lower bound to $1.20016$ by constructing an integrality gap instance for the CKR relaxation.
A technical challenge in improving the gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial $3$-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of $2$-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap.
One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondr\'{a}k that might be of independent combinatorial interest.
Kunszenti-Kovács Dávid (ELTE, Dept. of Applied Analysis and Computational Mathematics):
Metric inequalities in the theory of dense graph limits
In the theory of (dense) graph limits, several approaches to metric convergence have been explored over the years, including the cut metric, the jumble metric and density metric. In the bounded edge-weight case, these are all equivalent, but they start to diverge as soon as the boundedness assumption is lifted. The aim of the talk is present the motivation behind each of these metrics, and what their relationship is in the different generalizations.