| Name: | Mihir Dhanakshirur |
|---|---|
| Email: | mihird@iisc.ac.in |
| Home: | Indian Institute of Science, Bangalore |
| Project: | Generalizing the FKG Inequality |
| Mentors: | Siddhartha Sahi |
About My Project
Research Journal
First Presentation
Generalizing the FKG Inequality
Final Presentation
Extension of the FKG Inequality
Preliminary Readings
My project began in the first week of May with Professor Siddhartha suggesting I read papers [1] and [2] and refer to book [3]. These papers gave me a good background on distributive lattices, log-supermodular functions and the FKG inequality. The papers also suggested methods by which the FKG Inequality can be extended to more than just two functions. On Professor Siddhartha's advice, I began testing the extended version of the FKG Inequality on monotone boolean functions(MBFs) on Boolean lattices. This testing involved checking the inequality by varying the dimensions and the value of n in En(generalized FKG expression).
Week 1: May 31 - June 6
I spent a significant amount of time familiarising myself with Lattice Theory in order to better extend the representation theorems involved in distributive lattices and Boolean lattices. To do so, I referred to book [4]. I began reading [5] to understand some of the applications of the FKG Inequality. The paper talks about applying the FKG Inequality to investigate the properties of (i) log-supermodular functions (ii) Bernstein polynomials (iii) log convex sequences (iv) Tutte polynomials. I also presented my initial work on the project as part of our first presentation at DIMACS Center, Rutgers University. The powerpoint presentation can be found under the presentation heading.
Week 2: June 7 - June 14
I went to meet Professor Siddhartha at Princeton this week. We talked about certain properties that Fn might possess when treated as a functional going from a class of functions to positive reals. I started working with F3 and tested the validity of some of these properties on three variable monotone functions going from a Boolean Lattice to [0,1]. I am interested in exploring the applications the FKG Inequality may have in relationships between Tutte Polynomials. Exploring such relations requires a deeper understanding of Matroid Theory for which I will be referring to [6] and [7].
Week 3: June 15 - June 22
I showed that some of the properties that were conjectured to hold for Fn fail when we consider F3. I was able to generate counterexamples that disproved the validity of these properties. Some stronger conditions might need to be imposed in order for the conjectures to hold true. The conjecture itself might have been too restrictive and Siddhartha and I are looking to explore if a more general version exists. The coordinate-wise piecewise linear property might help in identifying characteristics of Fn. Matroid Theory is complex, but appears to be integral in bridging Linear Algebra and Graph Theory. [8] provides a good background on Tutte Polynomials and suggests further avenues which can be explored. I am particularly interested in the section "The Random Cluster Model", which references the FKG inequality extensively.
Week 4: June 23 - June 30
The functional Fn taking one variable monotone Boolean functions (going from the Boolean lattice to the interval [0,1]) to positive reals can be treated as a function going from the upper half of the unit plane to positive reals. Plotting this graph reveals some interesting properties regarding the functional. The figure is attached below.
Siddhartha hypothesizes that if a local minima for the function exists, it will be an element of a connected set of other local minima. I have been trying to test this hypothesis but it becomes far more difficult when the functional is taken on two variable monotone Boolean functions. I am also more comfortable handling matroid theory now and I have begun to explore various correlation inequalities in matroids. Perhaps there is a way to apply the extended version of the En correlation inequality to matroids (specifically, balanced matroids)? [9], [10] and [11] are papers that I found relevant to understanding the probabilistic method in matroids.
Week 5: July 1 - July 8
I worked on an algorithm to automatically check for certain kinds of minima for Fn. The cases when n>=3 are too complex at the moment since this would require treating them as a point in n*(2^d) space (n is the value in Fn and d is the dimension of the functions that make up the functional). Putative minima can be of two types: zero and nonzero minima. Zero minima are known to exist and are also very easy to find. It hasn't been showed if nonzero minima even exist, so I've been trying to develop an algorithm that searches for them. The process of developing an algorithm has given me a direction to look into in an attempt to formulate a proof to show that they do not exist. I reviewed [9] and now I'm focussing on [11] to get some inspiration on how to apply a stronger form of F3 in matroids. [11] is by June Huh who recently won the Fields Medal. I am excited to see if I can explore some of these possibilities with him.
Week 6: July 9 - July 16
I believe that I have come up with a simple proof to show that F2 for one dimensional boolean functions does not have nonzero local minima. The proof has also motivated a proof to show that F3 for one dimensional boolean functions doesn't have nonzero local minima either. The proof is still in a primitive state but some of the ideas and techniques might be helpful in generalizing it to higher dimensions.
Week 7: July 17 - July 24
I have completed the proof showing that F3 over one dimensional monotone Boolean functions has no non-zero minima. Handling the large number of cases involved in proving that non-zero minima do not exist for F3 over MBFs of any dimension is computationally complex. A simpler method suggested by Professor Siddhartha, might be to first shift individual entries (coordinate values that occur only in one function) and then attempt to shift shared entries (coordinate values that occur in more than one function). This is a more generalized method and it might lead to a more concise proof than trying to tackle the problem case by case. This week ended with participants of the DIMACs program presenting their work over the summer. You can find my final presentation under the presentation heading.
Post Program: July 24 -
References & Links
[1] "On the extension of the FKG inequality to n functions" by Elliott H Lieb and Siddhartha Sahi
[2] "Higher Correlation Inequalities" by Siddhartha Sahi
[3] "The Probabilistic Method" by Noga Alon and Joel H. Spencer
[4] "Introduction to Lattices and Order" by B.A. Davey and H.A. Priestley
[5] "Combinatorial applications of an inequality from statistical mechanics" by P.D. Seymour and D.J.A. Welsh
[6] "Matroid Theory" by James G. Oxley
[7] "What is a matroid" by James G. Oxley
[8] "The Tutte Polynomial" by Dominic Welsh
[9] "Balanced Matroids" by Tomas Feder and Milena Mihail
[10] "Negative Correlation in Graphs and Matroids" by Charles Semple and Dominic Welsh
[11] "Correlation bounds for fields and matroids" by June Huh, Benjamin Schröter and Botong Wang
Funding
This work was carried out while the author was a participant in the 2022 DIMACS REU program at Rutgers University, supported by the Rutgers Department of Mathematics[NSF Grant DMS-2001537].