Raziskovalni matematični seminar - Arhiv
| 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
We consider the problem of determining if a graph can be modified to a path by a small number of graph operations from some specified set S. If S only contains the edge contraction operation, we obtain the problem Path Contraction. A graph G is H-free for some graph H if G does not contain H as an induced subgraph. By combining known and new techniques we determine the complexity of Path Contraction on H-free graphs for every graph H. We do this by exploiting a relation to the problem of finding disjoint connected subgraphs, each containing some prescribed set of vertices. We compare our classification with the classifications for Hamilton Path, Long Path and Longest Induced Path on H-free graphs. The first two classifications are still incomplete and we will discuss relevant open problems. This is joint work with Walter Kern.
Join Zoom Meeting HERE!
For more info visit our YouTube Channel.
The f- and h-vectors of a simplicial complex are two important combinatorial invariants whose study has motivated a great deal of work in algebraic and topological combinatorics. The f-vector records the number of faces of the simplicial complex by dimension, while the h-vector is obtained from the f-vector by an invertible transformation. Although the entries of the f-vector of any complex have obvious combinatorial interpretations, the entries of the h-vector typically do not. However, if we impose stronger combinatorial conditions such as partitionability or the Cohen--Macaulay condition on the complex, then the entries of the h-vector are known to have combinatorial interpretations.
In this talk I will present joint work with Joseph Doolittle (Freie Universit\:{a}t Berlin) and Bennet Goeckner (University of Washington) in which we consider complexes that do not have these two properties. Given any $d$-dimensional simplicial complex $\Delta$, we construct another $d$-dimensional complex $\Gamma$ containing $\Delta$ such that $\Gamma$ and the relative complex $(\Gamma, \Delta)$ are (relatively) partitionable. This allows us to view the h-vector of $\Delta$ as the difference of h-vectors of partitionable complexes, and thus gives a combinatorial intepretation of its entries.
By contrast, there is a large class of complexes $\Delta$ for which there is no Cohen--Macaulay complex $\Gamma$ containing $\Delta$ such that $(\Gamma, \Delta)$ is Cohen--Macaulay. We give a complete characterization of when such $\Gamma$ exist, and give a straightforward description of all such $\Gamma$.
Finally, we consider the possibility of a similar construction for shellable complexes, and give a connection to Simon's conjecture on extendable shellability.
Join Zoom Meeting HERE!
For more info visit our YouTube Channel.
Let $G$ be a permutation group on a set $\Omega$. A base for $G$, is a subset $B$ of $\Omega$ such that the pointwise stabiliser of the elements of $B$ is trivial. There has been a large amount of recent research on the size of a base of a primitive permutation group, culminating with the recent proof of Pyber's Conjecture. At the same time there has been a large amount of work devoted to finding the primitive groups with a base of size two. For such groups we can define the Saxl graph of $G$ to be the graph with vertex set $\Omega$ and two elements are joined by an edge if they are a base. I will discuss some recent work with Tim Burness that investigates some of the properties of this graph.
Join Zoom Meeting HERE!
Everyone is welcome and encouraged to attend.
For more info visit our Website and our YouTube Channel.
This talk will cover certain applications of Boolean functions in cryptography and related research fields in this context. I will briefly mention the main research directions conducted by the staff at Centre of Cryptology at UP FAMNIT that include minimal linear codes, search for (more) perfect combinatorial objects, post-quantum cryptology and cryptanalysis. Future perspectives and development of Centre of Cryptology will also be briefly mentioned.
Join Zoom Meeting HERE!
For more info visit our YouTube Channel.
In early nineties C.Carlet introduced two new classes of bent functions, both derived from the Maiorana-McFarland (MM) class, and named them C and D class, respectively. Apart from a subclass of D and C, denoted by $D_0$ by Carlet, which is provably outside two main (completed) primary classes of bent functions, little is known about their efficient constructions. In this talk, I will give an overview of some known results, and present some new results, related to the bent functions in the C class, provably outside the completed MM class.
Join Zoom Meeting HERE!
Everyone is welcome and encouraged to attend.
For more info visit our Website and our YouTube Channel.
Linear codes have been widely used in communication systems since the beginning of the digital age. Mathematical research focused on error-correcting codes because of their important applications in data transmission. However, a special type of linear codes, called minimal, has proven to be useful for defining access structures in secret sharing schemes and secure two-party computation. This motivated research in this field.
Minimal codes can be constructed using a simple condition first proposed by Ashikhmin and Barg in 1998. Until the groundbreaking work of Ding, Heng and Zhou in 2018 there were no known examples of infinite families of minimal codes that violated this condition. Since then, several examples of such families have been constructed.
In this talk we present three generic constructions of families of minimal codes that violate Ashikhmin and Barg's condition based on characteristic functions of suitable sets. This is a joint work with E. Pasalic, F. Zhang and Y. Wei.
Join Zoom Meeting HERE!
For more info visit our YouTube Channel.
In the first part of the talk, we give basic definitions and properties of some cryptographically significant mappings, including (vectorial) bent functions, s-plateaued function, APN and AB functions as well as the notion of duals of bent and s-plateaued functions.
In the second part of the talk (joint work with Enes Pasalic and Samir Hodžić) we present some results and current research topics: Characterization of semi-bentness (bentness) of the component functions (duals of component functions) of the Gold AB function in spectral domain; Generic construction of vectorial bent functions motivated by the constructions of Zheng et al. (construction of vectorial bent functions) and Tang et al. (construction of bent functions).
Join Zoom Meeting HERE!
For more info visit our YouTube Channel.
This is the first in a series of seminars by members of the Center of Cryptography. Our research has many practical applications, and in the first lecture we will look at what motivates the development of post-quantum cryptography. Quantum computers are still a myth of some distant future for many, but in reality, standardisation of cryptographic algorithms that will be resistant to quantum attacks is already underway. It is expected that the migration to new algorithms will be a difficult and long process. But what will the first working quantum computer mean for our digital world? And how many currently implemented security algorithms will be broken?
Let us recall you that, due to the new measures at UP FAMNIT premises regarding the prevention of the spread of coronavirus, lectures at our Math Research Seminar will only be broadcasted via Zoom.
We are looking forward to meet at the video-conference throughout the following link:
Join Zoom Meeting HERE!
For more info visit our YouTube Channel.
This talk will consist of three parts.
In the first part of the talk (joint work with Valerio Boncompagni and Kristina Vušković), we present some recent structural and algorithmic results for several classes of graphs defined by forbidding certain "Truemper configurations" as induced subgraphs. (A _Truemper configuration_ is any theta, pyramid, prism, or wheel.)
In the second part of the talk (joint work with Frédéric Maffray and Kristina Vušković), we present a polynomial-time coloring algorithm for "rings." A ring is a certain generalization of a hyperhole, and it has the property that all holes in it are of the same length. (A _hole_ is an induced cycle of length at least four.) Rings originally appeared as a "basic" class in decomposition theorems for a couple of classes discussed in the first part of the talk.
In the third part of the talk, we discuss the structure of even-hole-free graphs of stability number at most three, and we present a polynomial-time coloring algorithm for these graphs.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or co-NP-hard when restricted to the class of diamond-free graphs:
Is a given clique strong?
Does the graph have a strong clique?
Is every vertex contained in a strong clique?
Given a partition of the vertex set into cliques, is every clique in the partition strong?
Can the vertex set be partitioned into strong cliques?
On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs:
Does every induced subgraph have a strong clique?
Is every maximal clique strong?
Is every edge contained in a strong clique?
The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdos-Hajnal property for such graphs.
Join Zoom Meeting:
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Pawel Komosa and Manuel Sorge.
A bramble in an undirected graph G is a family of connected subgraphs of G such that for every two subgraphs H_1 and H_2 in the bramble either V(H_1) intersects V(H_2) or there is an edge of G with one endpoint in V(H_1) and the second endpoint in V(H_2). The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble.
Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph G equals one plus the treewidth of G. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree n-vertex expander a bramble of order Ω(n^{1/2+δ}) requires size exponential in Ω(n^{2δ}) for any fixed δ \in (0,1/2]. On the other hand, the combination of results of Grohe and Marx, and Chekuri and Chuzhoy shows that a graph of treewidth k admits a bramble of order \widetilde{Ω}(k^{1/2}) and size \widetilde{O}(k^{3/2}). (\widetilde{Ω} and \widetilde{O} hide polylogarithmic factors and divisors, respectively.)
We first sharpen the second bound by proving that every graph G of treewidth at least k contains a bramble of order \widetilde{Ω}(k^{1/2}) and congestion 2, i.e., every vertex of G is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every δ \in (0,1/2], every graph G of treewidth at least k contains a bramble of order \widetilde{Ω}(k^{1/2+δ}) and size 2^{\widetilde{O}(k^{2δ})}.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
If you missed it, you can watch the lecture via the following link:
Passcode: K2@ZVpEY
Transmission of a vertex in a connected graph is the sum of distances from that vertex to all other vertices in the graph. While the use of transmissions as the basis for various topological indices is well known in mathematical chemistry, it is less known that transmissions have been used since 1970s also in space syntax, a particular field of architecture, to denote how easily one can get the sense of a whole building from a locally visible information. Besides these two applications, in this talk we will focus on recent theoretical results on transmissions in graphs, that are mostly related to questions of Klavžar and Dobrynin about graphs in which vertices have distinct transmissions.
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
In recent years, even-hole-free graphs were the object of much attention, however, many questions remain unanswered, such as the existence of a polynomial time algorithm for colouring even-hole-free graphs, or for finding a maximum stable set. The class of even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, K4)- free graphs was constructed, that still has unbounded tree-width [Sintiari and Trotignon, 2019]. The class has unbounded degree and contains arbitrarily large clique-minors. We ask whether this is necessary.
We show the class of even-hole-free graphs excluding a minor has bounded tree-width (1). This implies that planar even-hole-free graphs have bounded tree-width [da Silva and Linhares Sales, 2010]. To prove this, we provide an "induced grid theorem" for minor-free graphs.
We conjecture that for every d, the class of even-hole-free graphs of degree at most d has bounded tree-width, and we obtain partial results.
- The class of even-hole-free graphs of degree at most 3 has bounded tree-width.
- The class of (even-hole, pyramid)-free graphs of degree at most 4 has bounded tree-width.
In the meantime, our conjecture has been proven [Abrishami, Chudnovsky and Vuskovic, 2020].
Our second source of motivation for studying the tree-width of even-hole-free graphs stems from the area of property testing, namely, from the question whether even-hole-freeness is testable in the bounded degree model. Indeed, since our conjecture holds, this question is now answered.
In this talk I will explain the proof of (1), and give some background on property testing and testability of even-hole-freeness.
This is joint work with Pierre Aboulker, Frederik Harwath, Eunjung Kim, Noleen Köhler, Ni Luh Dewi Sintiari and Nicolas Trotignon.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
The slides of the talk are available HERE.
If you missed it, you can watch the lecture via the following link:
Passcode: kKx7cM?n
Abstract: Combinatorial shifting is a tool used to prove results from extremal set theory such as the Erdős-Ko-Rado theorem. Combinatorial shifting applies a step-by-step procedure to replace a system with a
somewhat simpler (shifted) system.
There are alternate algebraic approaches to shifting. For example, in recent work, I've shown how the Borel Fixed-Point theorem can in certain settings replace (in one step) a system with a shifted system.
In this talk, I'll connect the combinatorial shifting approach with the Borel Fixed-Point approach, by showing how to realize the step-by-step procedure of combinatorial shifting with a limiting
procedure of actions by 1-parameter matrices.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
Highly symmetric graphs are frequently studied in terms of the action of a specific type of group of automorphisms, as their structure is often completely determined by this action. Such is the case of a graph G admitting a group of automorphism X that acts transitively on its the arcs, or regularly on its vertices. If X is not vertex-transitive but partitions the vertex-set of G into orbits of equal size, then G can be (and usually is) studied through the theory of covering graphs. However, the case where X partitions the vertex-set of G into few orbits of different sizes is much less understood, and many of the classical tools used in the previously mentioned cases fall short. We give a general overview of the subject, and present new tools and possible lines of research to tackle the problem of classifying cubic graphs admitting a group of automorphisms with a few orbits (possibly of different sizes). We focus particularly on those graphs whose full automorphism group is transitive.
Link for the videoconference:
https://us02web.zoom.us/j/83916090638?pwd=Q3lkanVFZVhRTStnVW9Edi9lRmJhdz09
Many computationally hard graph problems can be solved efficiently after placing appropriate restrictions on the input graphs. One reason that might explain this jump in complexity is that the class of restricted inputs has bounded "width". There are several ways of defining a notion of "width", giving rise for example to well-known width parameters such as tree-width and clique-width.
In the talk, I will focus on the width parameter mim-width, introduced by Vatshelle. The modelling power of mim-width is stronger than that of clique-width, in the sense that graphs of bounded clique-width have bounded mim-width but there exist graph classes with bounded mim-width and unbounded clique-width. I will overview structural properties and algorithmic applications of this parameter and present recent joint work with Nick Brettell, Jake Horsfield, Giacomo Paesani and Daniël Paulusma.
The seminar was held by Zoom.
The slides of the talk are available in pdf at this link.
In a flexible (n_k) configuration at least one configuration line has the property that its k configuration points may be placed on it in k predetermined positions, while rearranging the rest of configuration in such a way that the point-line incidences are preserved.
We will show some useful applications of this concept in connection with Grünbaum incidence calculus. In particular, we will give a proof that for any k and for each sufficiently large number n, there exists an (n_k) configuration of points and lines.
This is joint work in progress with Leah Berman and Gábor Gévay.
Everyone is welcome and encouraged to join the video-lecture through the following link:
https://us02web.zoom.us/j/
The talk starts with the brief introduction of Mechanism Design theory, with particular focus on dominant strategy incentive compatible mechanisms. Next, the joint work with Prof. Dr. J. Čopič and Dr. M. Castellani is presented. We study the bilateral trade problem under no subsidies constraint which has not been explored much due to its complexity. In our setting, there are two traders, i.e., a seller and a buyer, one indivisible good, and a market maker. The traders have private valuations over one indivisible good and have a scarce information. A market maker is in full command of the choice of market platform and has no private information. We consider market equilibrium mechanisms, among which a special attention is devoted to stochastic bid-ask mechanisms. We conclude with an example that shows that in general a mechanism that maximizes a social welfare function may lie outside the set of simple posted prices mechanisms.
Link Zoom: https://us02web.zoom.us/j/86227923652
Terwilliger algebra of a commutative association scheme was successfully used for studying distance-regular graphs. However, this notion can be easily generalized to an arbitrary finite, simple and connected graph. In many instances, this algebra can be better studied via its irreducible modules. In this talk, we show how to relate the module structure of the Terwilliger algebra of a graph with the concept of local distance-regularity. Finally, we investigate how this algebra can be used as an effective tool for studying some combinatorial properties in the graph.
This is joint work with Stefko Miklavic.
Nut graphs are singular graphs of nullity one with full corresponding eigenvector. Recently, the existence problem of regular nut graphs was successfully addressed. In this talk, we present a generalisation of nut graphs to signed nut graphs and give some preliminary results of their existence. In particular, Fowler construction, switching equivalence and connection to double covers will be presented.
This is work in progress with Patrick W. Fowler, Irene Sciricha and Nino Bašić.
Link for the Conference: https://us02web.zoom.us/j/87925579576
A network consists of a graph and additional data on (properties of) nodes and/or links. In some applications, the values of properties can be structured objects such us intervals, compositions, sets of keywords, temporal quantities, etc.
Standard network description formats do not support such kinds of networks. We propose a JSON based format NetsJSON as a general network description option. It is supported in Python by a network analysis library Nets. The NetsJSON descriptions can be used as input data for network visualizations based on D3.js.
REFERENCES:
[1] Batagelj, V.: Python Packages for Networks. Encyclopedia of Social Network Analysis and
Mining. Reda Alhajj, Jon Rokne (Eds.), Springer, 2017
https://link.springer.com/referenceworkentry/10.1007%2F978-1-4614-7163-9_110210-1
[2] Batagelj, V., Maltseva, D.: Temporal bibliographic networks. Journal of Informetrics,
14(2020)1, 101006. https://www.sciencedirect.com/science/article/pii/S1751157719301439
[3] Batagelj, V.: Nets. https://github.com/bavla/Nets
[4] Batagelj, V.: NetsJSON. https://github.com/bavla/netsJSON
Link Zoom: https://zoom.us/j/297328207
Network-based adaptations of traditional compartmental infection models such as SIR or SEIR can be used to model the spreading of diseases between cities, countries or other geographical regions. One of the common challenges arising in these applications is the lack of available transmission probabilities between these geographical units. The task of inverse infection is the systematic estimation of these values. Several methods have been proposed recently for solving this task. One of them is the Generalized Inverse Infection Model (GIIM) [1]. GIIM offers a large amount of modeling flexibility and allows transmission probabilities to be defined as a function of known attributes, or risk factors in an epidemic context. In this presentation we will see how GIIM works in two specific real-life outbreaks.
Both examples are embedded in a geographical and temporal setting. The first one considers the 2015-2016 Zika virus outbreak in the Americas, where the countries and overseas territories of the continent form the nodes of the network and air travel routes define the links [2]. The second application models the 2009 H1N1 outbreak between the municipalities of Sweden, with links between the municipalities indicating frequent travel routes.
Our first goal in both of these studies is to discover the relationship between the transmission risk between geographical units and a variety of travel, environmental, meteorological and socioeconomic risk factors. Our second goal is to estimate the risk of exportation and importation of the diseases for the territories involved in these studies. We will show that the GIIM model is able to identify the most critical risk factors in both scenarios, and in the influenza study, it is able make predictions about future outbreaks with good accuracy.
REFERENCE:
1. A. Bóta, L. M. Gardner: A generalized framework for the estimation of edge infection probabilities. arXiv:1706.07532 (2017)
2. L. M. Gardner, A. Bóta, N. D. Grubaugh, K. Gangavarapu, M. U. G. Kramer: Inferring the risk factors behind the geographical spread and transmission of Zika in the Americas.PLoS Neglected Tropical Diseases.
http://journals.plos.org/plosntds/article?id=10.1371/journal.pntd.0006194
You should understand…
- I am talking not as an expert but as a long-time university lecturer who likes distance teaching and learning.
- Due to unusual circumstances, we are all pushed into distance learning and distance teaching. This serves as a good excuse to talk about such unusual topic at mathematics seminar.
- Throughout our University there are many disscussions about choosing appropriate tools for teaching courses via internet.
- We can imagine that such discussions take place in many other places in Slovenia and elsewhere on Earth.
I am not going to…
- ... promote one system over another one. [I hope some of you, will be able to do it soon at a similar seminar here or at some other location.]
- ... teach you how to use Powerpoint or Beamer, etc. for preparing your Seminar Talk.
- ... teach you how to organize your courses in moodle.
- ... teach you how to make and upload videos to Youtube on Vimeo.
So what I am going to do today?
- I will try to sketch a “theory” of communcation.
- Again, since I am not an expert in this area the word “theory” has to be taken cum grano salis.
- The goal of this talk is to give you enough theory that will explain
- why distance learning is difficult.
- why teaching large groups of students is more complicated than teaching small groups.
- why overusing colors and animation may be counter.
Everyone is welcome and encouraged to join the video-lecture via the following link:
https://zoom.us/j/479411024
A code is a subset of the vertex set of a graph. Given a code, the graph metric allows one to define an associated distance partition. Imposing combinatorial regularity conditions on the distance partition of a code leads to the definitions of the classes of s-regular and completely regular codes; analogously, algebraic symmetry conditions lead to the classes of s-neighbour-transitive and completely transitive codes. I will discuss previous results and current work related to characterising and classifying subclasses of 2-neighbour-transitive and completely transitive codes in Hamming graphs. All of the results I will discuss are part of ongoing effort to provide a full classification of completely transitive codes in Hamming graphs having minimum distance at least 5.
The BOSY project is addressing body (a)symmetries of athletes in different sport disciplines, including soccer, basketball, tennis, running and more. Local (single-joint or single-body part) and global asymmetries in muscle strength, power, flexibility and body stability are a very frequent phenomenon in athletes. Despite the increasing knowledge in the field of prevention and treatment, and represent one of the risk factors for sustaining an injury. Injuries have a detrimental effect both on an individual level, as athlete may be required to abstain from sport participation for significant amount of time, and on the level of clubs, sport associations and society, as injuries are often expensive to treat. Researchers within this project wish to contribute to the much needed knowledge on associations between (a)symmetries and sports injuries, and then further explore different measures for eliminating asymmetries and treating sports injuries.
Within the project, we are recruiting a large pool of athletes and carry out several test on them to seek for potential (a)symmetries. We are also retrospectively and prospectively examining the associations between the recognized asymmetries and occurrence of injuries. The test battery includes several aspects of physical ability and function (strength, power, balance, flexibility and kinematics of cyclic and acyclic movement patterns). The exceptionally large and rich dataset will enable to assess relationships, group differences, within-subject differences and other more complex calculations. With the aid of the experts of statistics and mathematics, the analyses could be stepped up to investigate potential patterns in the data that are not discoverable with common data processing methods. Additional insights, arising from such computations could reveal different, possibly more important and practically relevant information in terms of understating the underlying mechanisms of asymmetries and designing approaches to prevent injuries in sport.
Stanley introduced _supersolvable lattices_ in the 1970s to describe properties that certain lattices have in common with subgroup lattices of supersolvable groups. In recent work with Stephan Foldes, we have given a new characterization of supersolvable lattices in terms of lattice-theoretic analogues of normal subgroups. Our characterization simplifies and unifies existing literature on this class.
I'll introduce this class of lattices with motivating examples, and compare our characterization with existing ones.
10:00 – 10:45: FAMNIT-MP1
Lecturer: Stevan Pilipović
Title: Pseudo-differential operators-some new results.
Stevan Pilipović is an academician of the Serbian Academy of Sciences and Arts. His research interests include functional analysis, generalized functions and hyperfunctions, pseudo-differential operators, time-frequency analysis, linear and nonlinear equations with singularities, probability theory and stochastic processes.
11:00 – 11:45: FAMNIT-MP1
Lecturer: Gradimir V. Milovanović
Title: Orthogonality in the complex plane and some applications.
Gradimir V. Milovanović is a full member of the Serbian Academy of Sciences and Arts. His research is motivated by the range of topics among orthogonal polynomials and systems, interpolation theory and numerical analysis.
Euclidean distance geometry, that is the study of Euclidean geometry based on the concept of distance, is of current interest in several practical applications, such as molecular biology, wireless sensor networks, statics, data visualization and robotics. In this talk, we show how introductory algebraic geometry can be used as an effective tool for the solution of certain problems in Euclidean distance geometry.
A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases the toughness. Kriesell conjectured that for every minimally1-tough graph the minimum degree δ(G) = 2. It is natural to generalize this for other t values: Every minimally t-tough graph has a vertex of degree ceil(2t). In the present talk we investigate different questions related to this conjecture. The conjecture seems to be hard to prove, so we tried to prove it for some special graph classes. It turned out, that in some cases the conjecture is true because there are very few graphs that satisfy the conditions. On the other hand, we have evidence using complexity theory, that this is not the situation for some other graph classes. Many open questions remain.
This is joint work with Kitti Varga, István Kovács, Dániel Soltész.
In this talk, we introduce point-ellipse configurations and point-conic configurations. We present some of their basic properties and describe two interesting families of balanced point-conic 6-configurations. The construction of the first family is based on Carnot's theorem, whilst the construction of the second family is based on the Cartesian product of two regular polygons. Finally, we investigate a point-ellipse configuration based on the regular 24-cell.
This is joint work with Gábor Gévay, Jurij Kovič and Tomaž Pisanski.
