6 NOV 2024
14:00 - 15:00

The connection between excluding complete graphs (for various notions of exclusion) and the chromatic number of graphs is nearly a century old. In the 1940s, Hadwiger conjectured that a graph with no $K_n$-minor is $(n-1)$-colorable. Later, in the 1950s, Hajos proposed a strengthening of this conjecture, that every graph containing no subdivision of $K_n$ as a subgraph, is $(n-1)$-colorable. While both conjectures remain unresolved in some cases, a bound $c=c(n)$ (instead of $n-1$) for the chromatic number is known for every $n$ for both conjectures.
A natural attempt to strengthen this result would be to ask whether there exists a constant $c=c(n)$ such that every graph with no subdivision of $K_n$ as an induced subgraph is $c$-colorable. This question is a special case of Scott's conjecture from the 1990s. It was not until 2012 that the first non-trivial case, for $n=4$, was solved by Lev^eque, Maffray, and Trotignon.
In this talk, we present the solution to conjecture for $ngeq 5$ and describe the techniques used to achieve this result. This talk is based on joint works with Nicolas Trotignon, particularly the following: arXiv:2112.11970.

Zoom room information:
https://us06web.zoom.us/j/85237260136?pwd=MFSZoKdmRXAjfaSaBzbf19lTaaKglf.1
Meeting ID: 852 3726 0136
Passcode: 362880
Venue: Niavaran, Lecture Hall 1

31 OCT 2024
14:00 - 16:00

In this talk we provide a complete axiomatization of the Provability Logic for Heyting Arithmetic HA (this is the first-order intuitionistic fragment of the Peano Arithmetic PA). It turns out that the provability logic of HA is equal to iGL (intuitionistic fragment of the Gödel-Löb logic GL) plus ◻A → ◻B for some admissible rules A/B of iGL. Then we describe a crucial tool which was helpful during the completeness proof: a new Kripke style semantic for intuitionistic modal logics, called mixed semantics, which is a combination of derivability and usual validity in Kripke models.
This talk is based on the following two manuscripts: [1, 2].
[1] Mojtaba Mojtahedi. On provability logic of HA, 2022. https://arxiv.org/abs/ 2206.00445.
[2] Mojtaba Mojtahedi. Relative unification in intuitionistic logic: Towards provability logic of HA, 2022. https://arxiv.org/abs/2206.00446.

Zoom room information:
https://us06web.zoom.us/j/81916335336?pwd=5zQT4lutMiBoY5 Xp1pkFGtbqiaGozg.1
Meeting ID: 819 1633 5336
Passcode: 559618
Venue: Niavaran, Lecture Hall 1

30 OCT 2024
14:00 - 15:00

In this talk, we will discuss recent results concerning approximation algorithms for the Traveling Salesman Problem (TSP), with a focus on streaming and sublinear time algorithms. Additionally, we will examine the Maximum Join problem, including its weighted version, and explore its connection to TSP. This relationship can lead to improved approximation algorithms in streaming and sublinear time settings. We will also present our new results for TSP in these models.

Zoom room information:
https://us06web.zoom.us/j/85237260136?pwd=MFSZoKdmRXAjfaSaBzbf19lTaaKglf.1
Meeting ID: 852 3726 0136
Passcode: 362880
Venue: Niavaran, Lecture Hall 1

30 OCT 2024
17:30 - 19:00

In this talk, I will review several key concepts in Tropical Geometry, highlighting the naturality and numerous applications that arise when integrating the Theory of Positive Closed Currents into this framework. This talk is based on previous works with June Huh, Karim Adiprasito and ongoing joint work with Tien Cuong Dinh.

https://zoom.us/join
Meeting ID: 9086116889
Passcode: 362880
Venue: , (Zoom Lecture)

23 OCT 2024
14:00 - 15:00

An $r imes r$ {it $lambda$-Latin square} ({it rectangle}, respectively) is an $r imes r$ array in which each cell contains a multiset of $lambda$ elements from the set ${1,dots,r}$ of symbols such that each symbol occurs exactly $lambda$ times (at most $lambda$ times, respectively) in each row and column. Cavenagh, Hämäläinen, Lefevre, and Stones asked for conditions that ensure a simple λ-Latin rectangle can be extended to a simple λ-Latin square. We solve this problem in a more general setting by allowing the number of occurrences of each symbol to be prescribed. Cavenagh et al. also conjectured that for each r,λ there exists some n(r,λ) such that for any n ≥ n(r,k), every simple partial λ-Latin square of order r embeds in a simple λ-Latin square of order n. We confirm this conjecture.

Zoom room information:
https://us06web.zoom.us/j/85237260136?pwd=MFSZoKdmRXAjfaSaBzbf19lTaaKglf.1
Meeting ID: 852 3726 0136
Passcode: 362880
Venue: Niavaran, Lecture Hall 1

23 OCT 2024
16:00 - 17:00

Secret sharing is a cryptographic concept introduced in 1979. In a secret sharing scheme, a secret is distributed among a set of participants by giving each one a share. The shares are computed by applying a public rule to the secret and some randomness. Only certain pre-specified subsets of participants are qualified to recover the secret, while the secret remains hidden from all other subsets. Secret sharing is significant from both theoretical and practical perspectives. In this talk, I will survey our results from 2018 to 2024 and introduce several open problems.

Subscribing the Mathematics Colloquium mailing list:
https://groups.google.com/g/ipm-math-colloquium
Venue: Niavaran, Lecture Hall 1

17 OCT 2024
14:00 - 16:00



https://www.arxiv.org/abs/2408.15014
Zoom room information:
https://us06web.zoom.us/j/81916335336?pwd=5zQT4lutMiBoY5Xp1pkFGtbqiaGozg.1
Meeting ID: 819 1633 5336
Passcode: 559618
Venue: Niavaran, Lecture Hall 1

16 OCT 2024
15:30 - 17:00

The second order elliptic partial differential equations have been studied for more than a century. The most important and basic example of such equations is the Laplace equation. It is a linear equation related to many topics in mathematics and Physics. The main property of such an equation is that solutions of Laplace equations are regular. Another important example of elliptic equations is the Monge-Ampere equation which is fully nonlinear. In contrast to the Laplace equation, the solutions of the Monge-Ampere equation may fail to be smooth. In this talk, we go over basic properties of Monge-Ampere equations. At last we will go over the celebrated results of Caffarelli on interior regularity of solutions of the Monge-Ampere equation.
Venue: Niavaran, Lecture Hall 1