Timeline for Min max of a quadratic form of plus-minus ones
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 18, 2022 at 1:19 | comment | added | Paata Ivanishvili | @ShannonStarr, here is one way to get a lower bound, see Theorem of Defant--Mastylo--Perez applied to 2-homogeneous polynomial f, extremal010101.wordpress.com/2019/12/06/… Thanks for the references and the names. | |
| Jan 17, 2022 at 13:24 | comment | added | Shannon Starr | combinatorics.org/ojs/index.php/eljc/article/view/v19i4p10/pdf I think the idea of this paper could be useful. Break your $K_n$ graph into 2 roughly equal parts and focus on the $a_{ij}$'s between the two parts. After taking care of that, for choosing the matrix entries interior to each of the 2 parts, iterate. But that paper by Garry Bowlin probably does not have good enough results to be helpful. It is just a potentially interesting connection. | |
| Jan 17, 2022 at 11:49 | comment | added | Shannon Starr | @PaataIvanishvili That is impressive. I was wrong to quickly suggest the limit is 0. I would be interested in knowing your proof. I would think that some of the complexity people might be knowledgeable about this, like Cris Moore, or maybe Lenka Zdeborova. But also, the large-deviations people who are former students of Gerard Ben Arous should be interested, like Aukosh Jagganath, because you are proving lower bounds that rule-in or rule-out certain large deviation bounds. But you probably know better than me who to share this with. | |
| Jan 17, 2022 at 2:48 | comment | added | Paata Ivanishvili | @ShannonStarr I agree with upper bounds. Lower bounds are more tricky. I can show that liminf is at least $C>0$. If my calculus is correct then $C=2^{-5/2}$ works. Perhaps I can do better than $2^{-5/2}$, but these arguments that I know do not prove/disprove existence of the limit. | |
| Jan 17, 2022 at 0:04 | comment | added | Shannon Starr | The limsup is definitely finite by Talagrand's results (because if you chose the $A$ matrix randomly, instead of taking the minimum over all such $A$'s then the limit exists, and taking the minimum instead of the expectation is definitely no larger). One possibility is that the limit exists and equals 0. | |
| Jan 16, 2022 at 15:54 | history | edited | LSpice | CC BY-SA 4.0 |
Capitalise title
|
| Jan 16, 2022 at 15:46 | comment | added | Paata Ivanishvili | I added eigenvalues too. I wish I could also add: spin-glasses, polynomials, maxCut, Littlewoods 4/3 inequality, ... the limit of number of tags is <6 | |
| Jan 16, 2022 at 15:43 | history | edited | Paata Ivanishvili |
edited tags
|
|
| Jan 16, 2022 at 14:19 | comment | added | domotorp | Sorry, my bad, I take that part back. Still, I feel that this has more to do with eigenvalues than with discrepancy. | |
| Jan 16, 2022 at 12:44 | comment | added | Paata Ivanishvili | @domotorp why can you remove the absolute value? | |
| Jan 16, 2022 at 9:07 | comment | added | domotorp | As the absolute value does not really change anything (by symmetry), the answer to your question equals to $\frac 12 \lim_{n \to \infty}\, min_A max_x n^{-3/2} x^TAx$ where $A$ is an $n\times n$ size $\pm 1$ matrix and $x\in \{\pm 1\}^n$. Because of this, I think that you should use very different tags for your question. | |
| Jan 16, 2022 at 3:37 | history | asked | Paata Ivanishvili | CC BY-SA 4.0 |