Raziskovalni matematični seminar - Arhiv

Let Γ be a finite connected graph and G a vertex-transitive group of its automorphisms. The pair (Γ,G) is called locally-L if the permutation group induced by the action of the vertex-stabiliser G_v on the neighbourhood of a vertex v in Γ is permutation isomorphic to L. The maximum growth of | G_v | as a function of |V Γ | for locally-L pairs $( Γ,G)$ is called the graph growth of L. Recently, we have proven that if a transitive permutation group on a finite set Ω admits a proper block B such that the pointwise stabiliser of Ω\B in L is non-trivial, then the graph growth of L is exponential. In this talk, we discuss core ideas behind this result and illustrate its impact by providing an overview of graph growth types for transitive permutation groups of low degree.

This is joint work with Gabriel Verret.

This talk focuses on the construction of two new classes of plateaued functions, denoted by $\mathcal{C}$ and $\mathcal{D}_0$, both of which are derived from the $\mathcal{GMM}$ class.  We introduce the class $\mathcal{C}$ of $s$-plateaued functions defined as 

$$f(x, y) = x \cdot \phi(y) + 1_{L^{\perp}}(y),$$

where $0 < s < n$ and $L^{\perp}$ is a linear subspace of $\mathbb{F}_2^{\frac{n+s}{2}}$. This class is presented as a special subclass of the broader $\mathcal{D}$ class. 

Furthermore, we demonstrate that the subclass $\mathcal{D}_0$ can still be constructed even when the mapping $\phi$ is not injective. However, in this case, the sufficient conditions are more complicated than in the bent function.

In the final part of the talk, I present an initial approach for decomposing a plateaued function $f \in \mathcal{B}_n$ into four component functions $f_i \in \mathcal{B}_{n-2}$, for $i \in [1, 4]$. The 4-decomposition of a plateaued function $f = f1||f2||f3||f4 \in \cB_n$ is explained by describing three atmost cases:

1.     All component functions $f_i \in \mathcal{B}_{n-2}$ $(i \in [1, 4])$ are plateaued.
2.     All $f_i$ are functions with $5$-valued Walsh spectra.
3.     A mixed 4-decomposition.

This is a joint work with Enes Pasalic and Sadmir Kudin.

I will discuss work with Rachel Roberts and Melanie Stein.  If a 3-manifold M admits a Reebless foliation (a nice decomposition into surfaces) then the fundamental group of M acts without a global fixed point on a (not necessarily Hausdorff) simply connected 1-manifold, which is a tree-like object.  We showed that infinitely many hyperbolic 3-manifolds have fundamental groups that admit no such action, hence these manifolds do not admit a Reebless foliation.  I will aim to explain all of this to mathematicians not familiar with 3-manifold theory, concentrating on group actions.

Tree decompositions, and in particular path decompositions, are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph.

Families of bounded treewith and pathwidth have been completely characterized in terms of forbidden subgraphs (and minors) in the 1990s. Studying this question in connection with graph containment relations of more local flavor (such as induced subgraph or induced minors) is a relatively new research direction. In this talk we will present a recent result that provides a complete list of induced subgraph obstructions to bounded pathwidth.