Raziskovalni matematični seminar - Arhiv

In this talk we introduce Mathchem Python package, give a description of its functionality and provide examples of use Mathchem together with Sage to illustrate a workflow how to read and fi lter data, perform calculations and make some further analysis.

The package allows to read various molecular file formats, retrieve data from on-line the NCI database, import graph structure from Sage and NetworkX or parse a g6 string.

Download.

 A graph $X$ is said to be distance-balanced if for any edge $uv$ of $X$, the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$. These graphs were, at least implicitly, first studied by Handa who considered distance-balanced partial cubes. The term itself, however, is due to Jerebic, Klavžar, and Rall who studied distance-balanced graphs in the framework of various kinds of graph products.

We can generalize the definition of distance-balanced graphs to $n$-distance-balanced as follows. A graph $X$ is said to be $n$-distance-balanced if for any two vertices $u$ and $v$ of $X$ at distance $n$, the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$.

In this talk we present some results about $2$-distance-balanced graphs. In particular, we present the characterization of connected $2$-distance-balanced graphs which are not $2$-connected, and characterizations of $2$-distance-balanced cartesian and lexicographic products of two graphs.

This is a joint work with  Štefko Miklavič.

In  this talk we investigate  the possibility of constructing bent functions over fields with odd characteristic. We show that the necessary and sufficient bent conditions for both the Boolean function of the form

f (x)=Tr_1^{2k} ( x^{ 2^k - 1} + a x^{r (2^k - 1)} ) and the associated mapping

F (x)=Tr_k^{2k} ( x^{2^k - 1} + a x^{ r (2^k - 1)} ), where F: GF( p^{2k} ) --> GF( p^k ), are very similar and can be expressed in terms of the image of a set V used in the direct sum decomposition of GF( p^{2k} ).

Furthermore, we observe that  multiple output bent functions are easily constructed using the Maiorana-McFarland method.

Suppose a problem has been modeled as a Diophantine equation

D(x_1,...,x_n)=0

in any number n of unknowns, to be solved over the integers: here D can be a polynomial of any degree, with integer coefficients. It is not difficult to design a program which, given D, internally generates the n-tuples x_1,...,x_n of integers and prints the ones which solve the equation. The process can go on for ever---after all, there could be infinitely many solutions---, but what if we simply wanted to know whether the equation has a solution or not?

Finding an algorithm which, given D, says whether or not there is a solution, appeared tenth in a list of open problems proposed by David Hilbert at the beginning of the XX century. This challenge promoted theoretical investigations which contributed to the early developments of computer science.

Much like the more demanding Entscheidungsproblem, also Hilbert's Tenth received a negative answer: ``no such algorithm exists''.

This talk offers a historical recollection of the main achievements which led to this renowned negative result, often referred to as DPRM (Davis-Putnam-Robinson-Matiyasevich); those achievements have set up a formidable---but by no means abstruse---combinatorial machinery, teaching us how to model whatsoever computation by way of Diophantine polynomial equations.

Famous problems, such as the Goldbach conjecture, can be cast as assertions that some single Diophantine equation has no solution: they could have been settled, in principle, by a positive solution to Hilbert's Tenth. A joint paper by Davis, Matijasevi\v{c} and Robinson points the opposite direction: "all mathematical methods can be tools in the theory of Diophantine equations and perhaps we should consciously attempt to exploit them".

The idea of consistent colorings of the flags of a map with two colors has appeared previously in the literature in di ferent contexts. This talk present the definition of a flag bicoloring, a pseudo-orientation and the relation between this two concepts. Some related results are presented.