Discrete Mathematics 2010-2022

Abstract:

The Skolem Problem asks to determine whether a given integer linear recurrence sequence has a zero term. This problem, whose decidability has been open for 90 years , arises across a wide range of topics in computer science and dynamical system. In 1977, A generalization of this problem was made by Loxton and Van der Poorten who conjectured that for any $\epsilon >0$ and $\{u_n\}$ a linear recurrence sequence with dominant (s) roots $>1$ in absolute value, there is a effectively computable constant $C(\epsilon),$ such that if $ \vert u_n \vert < (\max_i\{ \vert \alpha_i \vert \})^{n(1-\epsilon)}$, then $n<C(\epsilon)$. Using results of Schmidt and Evertse, a complete non-effective (qualitative) proof of this conjecture was given by Fuchs and Heintze (2021) and, independently, by Karimov and al.~(2023). In this talk, we provide a survey on the study of Universal Skolem set and sketch the proof of the weak version of the conjecture by giving a effective upper bound of the number of solutions of that inequality extending Schmidt and Schlickewei previous works. The higher dimension of this conjecture will also be discussed in this presentation.


Joint work with Florian Luca, James Maynard, Joel Ouaknine and James Worrell.

Abstract:

A classical result by Erdős and Rényi from 1960 shows that the binomial random graph $G(n,p)$ undergoes a fundamental phase transition in its component structure when the expected average degree is around $1$ (i.e., around $p=1/n$). Specifically, for $p = (1-\varepsilon)/n$, where $\varepsilon > 0$ is a constant, all connected components are typically logarithmic in $n$, whereas for $p = (1+\varepsilon)/n$ a unique giant component of linear order emerges, and all other components are of order at most logarithmic in $n$.

A similar phenomenon — the typical emergence of a unique giant component surrounded by components of at most logarithmic order — has been observed in random subgraphs $G_p$ of specific host graphs $G$, such as the $d$-dimensional binary hypercube, random $d$-regular graphs, and pseudo-random $(n,d,\lambda)$-graphs, though with quite different proofs.

This naturally leads to the question: What assumptions on a $d$-regular $n$-vertex graph $G$ suffice for its random subgraph to typically exhibit this phase transition around the critical probability $p=1/(d-1)$? Furthermore, is there a unified approach that encompasses these classical cases? In this talk, we demonstrate that it suffices for $G$ to have mild global edge expansion and (almost-optimal) expansion of sets of (poly-)logarithmic order in $n$. This result covers many previously considered concrete setups.
We also discuss the tightness of our sufficient conditions.

Based on joint works with Joshua Erde, Mihyun Kang, and Michael Krivelevich.

Abstract:

Dear colleagues,

this is a kind reminder of the invitation to the

skip

Seminar on Analysis and Algebra Alpe-Adria (SAAAAJ)} on 19th October in Graz.



The SAAAAJ is a newly established, joint seminar between Zagreb, Ljubljana and Graz in both algebra and analysis.

skip


Date and location:} 19th October (Saturday), 10 am, at the TU Graz.\newline
(Lecture Room A (HS A) at Kopernikusgasse 24)

Schedule:}\newline
10:00–10:25: Amr Ali Al-Maktry (TU Graz) -- Polynomial functions on a class of finite non-commutative rings \newline
10:30–10:55: Andoni Zozaya (University of Ljubljana) -- Verbal problems in profinite groups \newline
11:00–11:25: Filip Najman (University of Zagreb) -- Modular curves \newline
----- Coffee break ----- \newline
12:00–12:25: Magdaléna Tinková (TU Graz / Czech Technical University) -- Artin twin primes \newline
12:30–12:55: Roman Drnovšek (University of Ljubljana) -- Positive Commutators on Banach lattices \newline
13:00–13:25: Kristina Ana Škreb (University of Zagreb) -- Dimensionless $L^p$ estimates for the Riesz vector \newline
14:00: joint lunch (restaurant Dionysos, Färbergasse 6)



Registration for lunch:} \newline
If you want to join the lunch at the restaurant, please register until 15th October.

skip

If you have any further questions, please do not hesitate to ask (frisch@math.tugraz.at and nicolussi@math.tugraz.at).

skip

We are looking forward to seeing you at the seminar!

\newpage

\section*{Location}
{ All talks will be in HS A in Kopernikusgasse 24 (first floor). The precise address is:
}
Kopernikusgasse 24
Graz University of Technology (TU Graz)
8010 Graz, Austria

skip

{ The address of the restaurant is:
}
Restaurant Dionysos
Färbergasse 6
8010 Graz, Austria


\section*{Abstracts}

{\bf Polynomial functions on a class of finite non-commutative rings}[2mm]
{\bf Amr Ali Al-Maktry (TU Graz)}


Let $R$ be a finite non-commutative ring with $1\ne 0$. By a polynomial function on $R$, we mean a function $F\colon R\longrightarrow R$ induced by a polynomial $f=\sum\limits_{i=0}^{n}a_ix^i\in R[x]$ via right substitution of the variable $x$, i.e.
$F(a)=f(a)= \sum\limits_{i=0}^{n}a_ia^i$ for every $a\in R$. In this paper, we study the polynomial functions of the free $R$-algebra
with a central basis $\{1,\alfa_1,\ldots,\alfa_k\}$ ($k\ge 1$) such that $\alfa_i\alfa_j=0$ for every $1\le i,j\le k$, $R[\alfa_1,\ldots,\alfa_k]$.
Our investigation revolves around assigning a polynomial $\lambda_f(y,z)$ over $R$ in non-commutative variables $y$ and $z$ to each polynomial $f$ in $R[x]$; and describing the polynomial functions on $R[\alfa_1,\ldots,\alfa_k]$ through the polynomial functions induced on $R$ by polynomials in $R[x]$ and by their assigned polynomials in the in non-commutative variables $y$ and $z$.
By extending results from the commutative case to the non-commutative scenario, we demonstrate that several properties and theorems in the commutative case can be generalized to the non-commutative setting with appropriate adjustments.[5mm]



{\bf Positive Commutators on Banach lattices}[2mm]
{\bf Roman Drnovšek (University of Ljubljana)}

We will present several results on positive commutators of positive operators on Banach lattices. We will start with the following finite-dimensional theorem. Let $A$ and $B$ be non-negative matrices such that the commutator $C = A B - B A$ is non-negative as well. Then, up to similarity with a permutation matrix, $C$ is a strictly upper triangular matrix, and so it is nilpotent. [5mm]






{\bf Modular curves}[2mm]
{\bf Filip Najman (University of Zagreb)}




Modular curves are moduli spaces of elliptic curves with prescribed images of their Galois representations. They are a key tool in studying torsion groups, isogenies and, more generally, Galois representations of elliptic curves. In recent years great progress, in many directions, has been made in our understanding of points on modular curves of low degree. In this talk I will describe some of these recent results, their consequences, as well as open problems in the field.[5mm]





{\bf Dimensionless $L^p$ estimates for the Riesz vector}[2mm]
{\bf Kristina Ana Škreb (University of Zagreb)}



We present a fundamentally new proof of the dimensionless $L^p$ boundedness of the Bakry Riesz vector on manifolds with bounded geometry. The key ingredients of the proof are sparse domination and probabilistic representation of the Riesz vector. This type of proof has the significant advantage that it allows for a much stronger conclusion, giving us a new range of weighted estimates. The talk is based on joint work with K. Domelevo and S. Petermichl. [5mm]




{\bf Artin twin primes}[2mm]
{\bf Magdaléna Tinková (TU Graz / Czech Technical University)}




In this talk, we will join two famous conjectures for primes, namely Artins conjecture on primitive roots and the Hardy--Littlewood two-tuple conjecture. In particular, we will study the existence and the asymptotic behavior of the number of prime pairs $p$ and $p+d$ with the same prescribed primitive root. This is joint work with Ezra Waxman and Mikuláš Zindulka.[5mm]




{\bf Verbal problems in profinite groups}[2mm]
{\bf Andoni Zozaya (University of Ljubljana)}


Given a group $G$ and a group word $w$ on $k$ variables, we can define a map $w \colon G^k \rightarrow G$ though substitution. Verbal problems study the relation between the image of this map and the subgroup it generates within $G$. In particular, we will study verbal conciseness – whether the subgroup is finite when the image of the map is finite – and strong verbal conciseness – whether the subgroup is finite when the image is countable – in the context of profinite groups.
We will introduce a new family of verbally concise groups, the so-called analytic groups; and, based on recent work with de las Heras, we will show that several classes of profinite verbally concise groups are, in fact, strongly verbally concise.[5mm]

Abstract:

We will discuss the typical behavior of $M$-Lipschitz functions on $d$-regular expander graphs, where an $M$-Lipschitz function means any two adjacent vertices admit integer values differ by at most $M$. While it is easy to see that the maximum possible height of an $M$-Lipschitz function on an $n$-vertex expander graph is about $C\cdot M \cdot \log n$, where $C$ depends (only) on $d$ and the expansion of the given graph, it was shown by Peled, Samotij, and Yehudayoff (2012) that a uniformly chosen random $M$-Lipschitz function has height at most $C’\cdot M \cdot \log \log n$ with high probability, showing that the typical height of an $M$-Lipschitz function is much smaller than the extreme case. Peled-Samotij-Yehudayoff’s result holds under the condition that, roughly, subsets of the expander graph expand by the rate of about $M \cdot \log (dM)$. We will show that the same result holds under a much weaker condition assuming that $d$ is large enough. This is joint work with Robert Krueger and Lina Li.

Abstract:

For a class of weighted infinite metric trees we propose a definition of the boundary trace which maps $H^1$-functions on the tree to $L^2$-functions on a compact Riemannian manifold. For a range of parameters, the precise Sobolev regularity of the traces is determined. This allows one to show the well-posedness for a Laplace-type equation on infinite trees interacting with Euclidean domains through the boundary. Based on joint works with Valentina Franceschi (Padova), Maryna Kachanovska (Paris) and Konstantin Pankrashkin (Oldenburg).