Raziskovalni matematični seminar - Arhiv

The Erdős-Ko-Rado theorem describes the largest family of pairwise-intersecting k-element subsets of a fixed base set: for small k, this is the family of all sets containing some common element.  The Hilton-Milner theorem describes what happens if we disallow a common element.

I will present recent progress from joint work with Denys Bulavka and Francesca Gandini on the Hilton-Milner theorem and extensions.

In this talk, we present an interesting correspondence between partially symmetric 3×3×r tensors over Fq (for r≤6), linear systems of conics in PG(2,q), and subspaces of PG(5,q). We review the history of classifying these linear systems in PG(2,q) up to projective equivalence, an open problem dating back to 1908. We outline recent advances, showing how properties of the quadric Veronesean in PG(5,q) can be utilized to identify a set of complete invariants for projectively inequivalent pencils and webs of conics in PG(2,q).  These results contribute to the classification of partially symmetric 3x3xr tensors over Fq under the action of the group stabilising rank-1 tensors.

A linear map between matrix spaces is called completely positive (cp) if it preserves positive semidefiniteness, even when ampliated to higher-dimensional spaces. In this talk we demonstrate how cp maps are closely related to a particular class of convex sets: the solution sets of linear matrix inequalities (LMIs), known as spectrahedra.
Spectrahedra generalize polyhedra and have gained prominence since the 1990s due to their central role in semidefinite programming (SDP). The main result will explain how a cp map gives rise to a linear Positivstellensatz certificate and vice-versa.
The talk is based on joint works with Bill Helton and Scott McCullough.

In this talk, we will describe a construction of some combinatorial structures, especially regular graphs and digraphs, using finite groups. We will point out some interesting results obtained by using some particular finite groups. Further, we will show how some of the obtained combinatorial structures can be described geometrically.

These are exciting times for cryptography!

For the first time in a long time new asymmetric cryptography algorithms were standardised by NIST (National Institute of Standards and Technology). In the talk we will explain: Why was this necessary? How do these algorithms behave? Will the future of cryptography even involve solutions based on quantum mechanics?

In a nucleation process, formation of small nuclei initiates displacement of one equilibrium by another. Typically, nucleation is local: diameter of the nuclei is much smaller than the time-scale of convergence to the new state. We will discuss a few simple models in which this is not true; instead, the nuclei generate lower-dimensional structures that grow and interact significantly before most of the space is affected. Analysis of such models includes a variety of combinatorial and probabilistic methods.

The talk will be aimed at the general audience.

Richard Stanley initiated the study of the chromatic symmetric function X_G of a finite graph G.  This symmetric function encodes more information about G than the well-studied chromatic polynomial, and has been studied closely.  Michelle Wachs and I introduced a refined version of X_G.  For most graphs G, this refined version is quasisymmetric but not necessarily symmetric.  However, X_G is symmetric when G is an indifference graph.  Chromatic quasisymmetric functions of indifference graphs are related to previously studied objects from algebraic geometry and representation theory of symmetric groups.  After introducing  chromatic symmetric and quasisymmetric functions, I will discuss these relations.

Given a family of graphs F, we define the F-saturation game as follows. Two players alternate adding edges to an initially empty graph on n vertices, with the only constraint being that neither player can add an edge that creates a subgraph in F. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let sat_g(n,F) denote the number of edges that are in the final graph when both players play optimally. In general, there are very few non-trivial bounds on the order of magnitude of sat_g(n,F). In this work, we find collections of infinite families of cycles C such that sat_g(n,C) has a linear growth rate.

Joint work with Sean English, Grace McCourt, Erin Meger, Michael S. Ross, and Sam Spiro.

I will give a general overview of recent developments in number theory, with many old and new results being proved through the lens of multiplicative functions. Many deep unsolved problems about primes such as the Riemann Hypothesis and the Twin Prime Conjecture are intimately connected with the Möbius function. Viewing the latter as simply one instance of a multiplicative function satisfying certain properties and developing a general theory of multiplicative functions has been very fruitful – most classical results in analytic number theory have been reproved in this framework, without appealing to the analytic continuation of the Riemann zeta function (or more general L-functions). In particular, one may adapt a probabilistic viewpoint and consider so called random multiplicative functions taking the values +1 and -1 on the primes randomly. This was initiated by Wintner, who proved the analogue of the Riemann Hypothesis in this simplified setting. Later this was further developed by Harper, who considered finer distributional questions. If time permits, I will present results on the Twin Prime analogue in this probabilistic setting, based on ongoing joint work with Jake Chinis.

Width parameters such as treewidth, the most prominent width parameter, are graph invariants that roughly measure how complicated a graph is. Several width parameters have algorithmic implications; for example, many NP-hard problems can be solved in polynomial time in graphs of bounded treewidth. On the other hand, there exist graph classes with unbounded treewidth but which do admit fast algorithms for hard problems, so in this sense treewidth does a poor job of capturing the solvability of hard problems. Several new width parameters have recently been introduced to better represent the solvability of the maximum independent set problem. In this talk, I will discuss results and problems related to one of these width parameters, called induced matching treewidth.

This talk is based on joint work with Marcin Briański, Jadwiga Czyżewska, Rose McCarty, Martin Milanič, Paweł Rzążewski, and Bartosz Walczak.

In this talk, we address the algebraic method to design plateaued functions with desirable cryptographic properties (such as maximal algebraic degree and balancedness) by employing the generalized Maiorana-McFarland class (GMM) of Boolean functions. We consider functions in the GMM class of the form $f(x,y)=x \cdot \phi(y) \oplus h(y)$, where $x \in \F_2^{n/2+k}, y \in \F_2^{n/2 -k}$ and $\phi(y): \F_2^{n/2 -k} \rightarrow \F_2^{n/2 +k}$, and derive a set of sufficient conditions for designing optimal plateaued functions. We will show that under certain conditions designed optimal plateaued functions do not admit the linear structures. Furthermore, we will show that under specific conditions, the addition of an indicator ($1_{R}(x,y) = 1_{E_1}(x)1_{E_2}(y)$) to a function $g(x,y) = x \cdot \phi(y)$, we have that $f(x,y) = g(x,y) \oplus  1_{R}(x,y)$ is a plateaued function.

We introduce Boole's problem, and the reasonably large literature related to it. We then recall an old result of Renyi (1962) that we prefer to call "a zero-one lemma", and show that it can provide a simple, elementary (short, high school level) proof for most of the results in the extensive literature about this problem. We also derive a few new results with the help of this powerful lemma. 

This work in progress explores graphs that can be drawn in the Euclidean plane exhibiting non-trivial geometric symmetry. We investigate the significance of semiregular and quasi-semiregular automorphisms for achieving such symmetric embeddings. We consider both cyclic and dihedral symmetries.

Get ready for an exhilarating opportunity this April!  Professor Marston Conder from New Zealand will grace FAMNIT with his presence to deliver an insightful mini-course on MAGMA, the powerful computational algebra system.

Course Outline:
Overview of MAGMA and its applications, including graphs, digraphs, and Cayley graphs.
Handling permutation groups, matrix groups, and groups of small order.
Exploring finitely presented groups and their practical applications.

Plus, exciting demonstrations showcasing the practical usage of MAGMA will be included!

Mark your calendars! Here's the schedule:

Monday, April 15th: FAMNIT-VP1
- Opening: 9:50 - 10:00
- MAGMA 1: 10:00 - 11:00
- Coffee break: 11:00 - 11:30
- MAGMA 2: 11:30 - 12:30
- Lunch: 12:30 - 14:00
- MAGMA 3: 14:00 - 15:00
- Coffee break: 15:00 - 15:30
- MAGMA 4: 15:30 - 16:30

Tuesday, April 16th:FAMNIT-MP1
- MAGMA 5: 10:00 - 11:00
- Coffee break: 11:00 - 11:30
- MAGMA 6: 11:30 - 12:30
- Closing remarks: 12:30 onwards

Who Should Attend?
These lectures are perfect for students specializing in Algebraic graph theory, young PhDs, postdocs, and anyone interested in cryptography!
 

A graph H is common if the number of monochromatic copies of H in a 2-edge-coloring of the complete graph is asymptotically minimized by the random coloring. The classification of common graphs is one of the most intriguing problems in extremal graph theory. We study the notion of weakly locally common graphs considered by Csóka, Hubai, and Lovász [arXiv:1912.02926], where the graph is required to be the minimizer with respect to perturbations of the random 2-edge-coloring. We give a complete analysis of the 12 initial terms in the Taylor series
determining the number of monochromatic copies of H in such perturbations and classify graphs H based on this analysis into three categories:
   *   Graphs of Class I are weakly locally common.
   *   Graphs of Class II are not weakly locallycommon.
   *   Graphs of Class III cannot be determined to be weakly locally common or not based on the initial 12 terms.
As a corollary, we obtain new necessary conditions on a graph to be common and new sufficient conditions on a graph to be not common.
Joint work with Robert Hancock, Daniel Král’, and Jan Volec.

 Let's dive into the fascinating world of locally common graphs together!

Canonical double cover BX of a graph X is the direct product of X with K_2 (the complete graph on two vertices). Automorphisms of the base graph X naturally lift to automorphisms of BX. In addition, there is an obvious involutory automorphism of BX swapping the bipartition sets. Expected automorphisms of BX are those that can be obtained by combining the above two types, and generate a group isomorphic to Aut(X) × S_2. If BX has only the expected automorphisms, then X is called stable, and it is called unstable otherwise. Characterization of stable graphs is an open problem, even when restricted to special graph classes like circulant graphs. In this talk, I will present several constructions of unstable graphs and characterizations within certain graph families, with special emphasis on circulant graphs. I will show the connection of this problem with Schur rings.

Everyone is welcome and encouraged to attend!

We will present a recent approach on matrix representation of hypercomplex regular functions. This topic has been also considered independently by A. Altavilla and  C. de Fabritiis. In this talk, we will explore many applications and potential outcomes of these new representations.
We will start by recollecting ideas on several possible ways of representing complex and hypercomplex (namely quaternionic and octonionic) numbers and how these ideas can be - in some sense - transposed to (some classes of) hypercomplex regular functions.
The seminar is supposed to be self-contained with little knowledge of basic complex analysis.
This is a jont work with Jasna Prezelj.

Everyone is welcome and encouraged to attend!

In this talk, a graph Γ = (V, E) is a finite simple graph, which means that V is a finite set and E is a family of its subsets that have two elements. Given two graphs Γ1 = (V1, E1) and Γ2 = (V2, E2), a map Φ : V1 → V2 is
a homomorphism if {Φ(u), Φ(v)} ∈ E2 whenever {u, v} ∈ E1. A bijective homomorphism is an isomorphism in the case {Φ(u), Φ(v)} ∈ E2 if and only if {u, v} ∈ E1. As usual, if Γ1 = Γ2, then a homomorphism/isomorphism is
an endomorphism/automorphism. A core of a graph Γ is any its subgraph Γ0 such that a) there exists some homomorphism from Γ to Γ0 and b) all endomorphisms of Γ0 are automorphisms.
In graph theory, Γ1 and Γ2 are usually treated as ‘equivalent’ if they are isomorphic, i.e. if there exists some isomorphism between them. Less frequent we meet the notion of homomorphically equivalent graphs Γ1, Γ2,
which means that there exists a graph homomorphism Φ : V1 → V2 and a graph homomorphism Ψ : V2 → V1. Here, the notion of a core appears very naturally because two graphs are homomorphically equivalent if and
only if they have isomorphic cores. Often, it is very difficult to decide if there exists a homomorphism between two graphs. In fact, this problem is related to many graph parameters that are hard to compute, such as the
chromatic/clique/independence number. As a result, the study of cores is challenging. In this talk, I will survey some properties of cores, with an emphasis on graphs that either admit a certain degree of ‘symmetry’ or have
‘nice’ combinatorial properties.

Everyone is welcome and encouraged to attend.

Let $ Q_{n}(\CC) $ be the space of all $ n\times n $ alternate matricesvover the complex field $ \CC $ and let $ d_{\chi}(A) $ denote the immanant of the matrix $ A \in Q_{n}(\CC) $ associated with the irreducible character $ \chi $ of the permutation group $ S_{n} $‎. ‎The main goal in this paper is to find all the irreducible characters
such that the induced immanant function $ d_{\chi} $ vanishes identically on $ Q_{n}(\CC) $‎.

This is a joint work with Bojan Kuzma.

Everyone is welcome and encouraged to attend.

A minimal surface in a Euclidean space $\mathbb R^n$ for $n\ge 3$ is an immersed surface which locally minimizes the area. Every oriented minimal surface is parameterized by a conformal harmonic immersion from an open Riemann surface, and vice versa. In this talk, I shall present a recent result on the existence of minimal surfaces of a given conformal type having a given finite group of symmetries induced by orthogonal transformations on $\mathbb R^n$.

Everyone is welcome and encouraged to attend.