110
$\begingroup$

Update: Please restrict your answers to "tweets" that give more than just the statement of the result, and give also the essence (or a useful hint) of the argument/novelty.

I am looking for examples that the essence of a notable mathematical development fits a tweet (140 characters in English, no fancy formulas).

Background and motivation: This question was motivated by some discussion with Lior Pachter and Dave Bacon (over Twitter). Going over my own papers and blog posts I found very few such examples. (I give one answer.) There were also few developments that I do not know how to tweet their essence but I feel that a good tweet can be made by a person with deep understanding of the matter.

I think that a good list of answers can serve as a good educational window for some developments and areas in mathematics and it won't be overly big.

At most 140 characters per answer, single link is permitted. Tweeting one's own result is encouraged.

Update: I learned quite a few things, and Noam's tweet that I accepted is mind-boggling.

Improve this question
$\endgroup$
29
  • 180
    $\begingroup$ I have discovered a truly remarkable proof of this theorem which this Tweet is too small to contain. $\endgroup$
    – Glorfindel
    Commented Apr 26, 2017 at 8:26
  • 46
    $\begingroup$ I feel like most of the answers are mis-interpreting the question. This doesn't ask for a result whose statement is in 140 characters; that would be too broad: most paper titles fit in them. It asks for a result whose essence is tweetable: given the tweet alone, a mathematician with good knowledge of the field can fill in the details and complete a proof. So I am going to downvote almost all of them. $\endgroup$
    – Federico Poloni
    Commented Apr 26, 2017 at 10:16
  • 13
    $\begingroup$ @FedericoPoloni: what is it, a kind of joke? Could you please indicate to me where exactly in the question it is written that the tweet should be such that "a mathematician with good knowledge of the field can fill in the details and complete a proof"? Honestly, I do not think that your personal interpretation of the locution "essence of a notable mathematical development" should be taken as a rule here. $\endgroup$
    – Francesco Polizzi
    Commented Apr 26, 2017 at 10:21
  • 15
    $\begingroup$ Perhaps the next big MO question should be, "What is the essence of a mathematical result?" I myself lean toward Federico's interpretation- pithifying a theorem's statement does not necessarily clarify or illuminate the ideas at play. $\endgroup$
    – Neal
    Commented Apr 26, 2017 at 12:52
  • 30
    $\begingroup$ My initial intention was indeed that the "tweet" gives more than just the statement of the result but also the essence of the argument/novelty. To demand that a mathematician in the field can fill the details is too much to ask for. $\endgroup$
    – Gil Kalai
    Commented Apr 26, 2017 at 12:58

89 Answers 89

Reset to default
1
2 3
104
$\begingroup$

Every rational r is xyz(x+y+z) for some rational x,y,z.
Proof: Euler (1749) found x(r),y(r),z(r). Nobody knows how.

I have a guess. https://people.math.harvard.edu/~elkies/euler_14t.pdf

Improve this answer
$\endgroup$
2
  • 10
    $\begingroup$ And there are some simpler than Euler's x(r), y(r), and z(r). See mathoverflow.net/q/302933/24165 . $\endgroup$
    – Anton Klyachko
    Commented Jul 20, 2018 at 4:05
  • 10
    $\begingroup$ Thank you for that reference. I already found x,y,z a bit simpler than Euler's, but not nearly that simple! Now I should revisit this to figure out if and how the Klyachko-Mazhuga-Ponfilenko fits into the elliptic-fibration picture . . . $\endgroup$
    – Noam D. Elkies
    Commented Jul 20, 2018 at 5:01
180
$\begingroup$

Four color theorem: any planar graph can be colored with 4 colors. Only proof by computer. SAD.

Improve this answer
$\endgroup$
7
  • 5
    $\begingroup$ Expressing the essence of how it can be reduced to a huge finite problem for computer proof would be nice, though... $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Commented Apr 26, 2017 at 16:37
  • 11
    $\begingroup$ As years pass by (and more so if we go outside USA) the probability that someone gets the pun tends to zero. SAD. $\endgroup$
    – leonbloy
    Commented Apr 29, 2017 at 13:14
  • 2
    $\begingroup$ ??????????????? $\endgroup$
    – Lutz Mattner
    Commented Mar 3, 2018 at 23:45
  • 5
    $\begingroup$ @LutzMattner It's a political joke about Donald Trump, president of America (2016-202?). He likes to say "SAD!" and it's made into jokes. $\endgroup$
    – MaudPieTheRocktorate
    Commented May 28, 2019 at 5:13
  • $\begingroup$ Many such cases! $\endgroup$
    – C7X
    Commented Jul 30, 2023 at 20:37
123
$\begingroup$

27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵. Nice try, Euler. link

#Counterexamples

Improve this answer
$\endgroup$
6
  • 8
    $\begingroup$ You can shorten it and make it friendlier to read using Unicode superscript numeral characters. $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Commented Apr 26, 2017 at 16:34
  • 2
    $\begingroup$ How do we do it? (without using Tex, say on Twitter) $\endgroup$
    – Gil Kalai
    Commented Apr 26, 2017 at 17:34
  • 5
    $\begingroup$ 27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵. $\endgroup$
    – Ahmed Fasih
    Commented Apr 26, 2017 at 20:13
  • 1
    $\begingroup$ @GilKalai you can express x to the n as x^n with the use of the caret $\endgroup$
    – Restioson
    Commented Apr 29, 2017 at 7:31
  • 2
    $\begingroup$ @Restioson: I originally typed it out that way, but R.. commented that it is in fact possible to tweet superscript numerals, so I changed it to make it more readable. I was able to type out the superscript 5's in my answer -- without MathJax -- by copy/pasting from this website: txtn.us/tiny-text. $\endgroup$
    – Will Brian
    Commented May 1, 2017 at 13:46
117
$\begingroup$

The sentence "The first positive integer that cannot be specified in a 140 character tweet" doesn't specify a well defined integer.

Improve this answer
$\endgroup$
6
  • 45
    $\begingroup$ In other words, "There are non-tweetable positive integers, but there is no smallest non-tweetable positive integer. Contradiction." $\endgroup$
    – Fedor Petrov
    Commented Apr 27, 2017 at 14:17
  • 2
    $\begingroup$ Forgive my ignorance, but assuming a base-10 representation, is 10^140 not the smallest non-tweetable positive integer? $\endgroup$
    – ayane_m
    Commented Apr 28, 2017 at 5:42
  • 3
    $\begingroup$ We mean tweetability in plain languages and mathematical formulae, not just base-10 representations. $\endgroup$
    – Fedor Petrov
    Commented Apr 28, 2017 at 6:23
  • 15
    $\begingroup$ You can tweet: "Ten to the power 140" $\endgroup$
    – Gil Kalai
    Commented Apr 28, 2017 at 6:24
  • 8
    $\begingroup$ @彩音M en.wikipedia.org/wiki/Berry_paradox $\endgroup$
    – math no more
    Commented Apr 28, 2017 at 6:26
91
$\begingroup$

Not deep, but if [0,1]² is cut in N triangles of equal area, N is even. If not, extend 2-adic valuation on Q to R, tricolor plane and apply Sperner.

Improve this answer
$\endgroup$
3
  • 18
    $\begingroup$ This is my favorite! Perhaps it would even benefit from removing the humble "Not deep". $\endgroup$
    – Moritz Firsching
    Commented Apr 26, 2017 at 16:44
  • 4
    $\begingroup$ I like it too, and it suggests a nice general pattern for tweetable mathematics: (1) Statement, (2) Setup, (3) "Apply [known result]." $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Commented Apr 27, 2017 at 2:43
  • 8
    $\begingroup$ #MonskysTheorem $\endgroup$
    – Igor Rivin
    Commented May 6, 2017 at 3:28
90
$\begingroup$

Chebyshev said, and I say it again,
there is always a prime between n and 2n.
#BertrandsPostulate

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Where n = 0? If you have space, maybe include that n > 0 $\endgroup$
    – Restioson
    Commented Apr 29, 2017 at 7:32
  • 2
    $\begingroup$ Well, its not really me who invented this tweet... (Also, then I should perhaps also include that $n$ is a natural number and not from some unique factorization domain or whatever) $\endgroup$
    – Moritz Firsching
    Commented Apr 29, 2017 at 7:40
  • $\begingroup$ yeah, there just might not be enough chars for that... $\endgroup$
    – Restioson
    Commented May 1, 2017 at 13:16
  • 11
    $\begingroup$ I wish Paul Erdos had a twitter account. $\endgroup$
    – Santi Spadaro
    Commented Apr 27, 2019 at 23:56
85
$\begingroup$

Integral of exp(-x²) dx over R = Γ(1/2) = √π. Proof: square the Gaussian integral and use polar coordinates!

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ This is a great example! $\endgroup$
    – André Henriques
    Commented Apr 27, 2017 at 21:29
65
$\begingroup$

Erdos: You can color edges between √2ᵏ vertices red/blue so no monochrome size k subgraphs (Pick a random coloring. It probably works)

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Perfect example! I love this one. $\endgroup$
    – Steven Stadnicki
    Commented Apr 27, 2017 at 0:04
  • 8
    $\begingroup$ It's even a counterexample to Gil Kalai's comment that "To demand that a mathematician in the field can fill the details is too much to ask for." $\endgroup$
    – Noam D. Elkies
    Commented Apr 29, 2017 at 14:12
58
$\begingroup$

The n-th binary digit of π is calculable without calculating all the previous digits.

Improve this answer
$\endgroup$
2
48
$\begingroup$

There are infinitely many primes p for which there is a prime between p+1 and p+246.

Improve this answer
$\endgroup$
2
  • 24
    $\begingroup$ One can add "Still want to know about p+3". $\endgroup$
    – Gregory Arone
    Commented May 6, 2017 at 15:00
  • 1
    $\begingroup$ The reference would fit too: arxiv.org/abs/1407.4897 $\endgroup$
    – user44143
    Commented Apr 16, 2019 at 13:36
42
$\begingroup$

Euclid: there are infinitely many primes, if not, multiply all and add 1. Link

If only they had Twitter back then. They had so many tweetable proofs :)

Improve this answer
$\endgroup$
5
  • 62
    $\begingroup$ There are infinitely many composites: Multiple the first n of them. Don't add 1 (attributed to Hendrik Lenstra) $\endgroup$
    – David
    Commented Apr 27, 2017 at 20:43
  • 9
    $\begingroup$ @JavaMan: that proves that if there are at least two composites, then there are infinitely many… $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Apr 29, 2017 at 23:09
  • 3
    $\begingroup$ Also, don't forget xkcd. $\endgroup$
    – Ivo Terek
    Commented Apr 30, 2017 at 22:18
  • 2
    $\begingroup$ Better: "Euclid: there are arbitrarily many primes, by multiplying those given and adding 1." $\endgroup$
    – user44143
    Commented May 1, 2017 at 18:56
  • 9
    $\begingroup$ This phrasing can support a common misunderstanding of the proof though. I would end with: "...and add 1; then factor." $\endgroup$
    – usul
    Commented Nov 16, 2017 at 17:45
41
$\begingroup$

33 = 8866128975287528³ + (-8778405442862239)³ + (-2736111468807040)³. Andrew Booker! link.

Update 2019-09-05: $(-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3 = 42$, https://people.maths.bris.ac.uk/~maarb/. This completes all the numbers less than $114$.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ This is fantastic!!!!! (Read the link if you didn't already know why.) Honestly, this looks like a winning answer. $\endgroup$
    – Todd Trimble
    Commented Mar 9, 2019 at 14:20
  • 2
    $\begingroup$ Tim Browning deserves a tradable digital trophy for this solution. This is a computational problem which is easy to verify, difficult to solve, and of mathematical significance. One should be able to construct a cryptocurrency smart contract that can reward someone for solving this kind of problem. mathoverflow.net/questions/322022/… $\endgroup$
    – Joseph Van Name
    Commented Mar 9, 2019 at 14:30
  • 4
    $\begingroup$ @JosephVanName I do really like and like to think about your linked question - however, as you kind of hinted at, if Andrew Booker were to be awarded merely for his solution, he would be demotivated to actually publish his methods, lest others copy! $\endgroup$
    – Mark S
    Commented Mar 10, 2019 at 23:45
  • 3
    $\begingroup$ mathoverflow.net/a/223121/88133 $\endgroup$
    – Zach Teitler
    Commented Sep 6, 2019 at 1:21
39
$\begingroup$

The most beautifully useless theorem of mathematics IMO:

"This statement is a theorem (and moreover, I can prove it)" — link

Improve this answer
$\endgroup$
3
  • 10
    $\begingroup$ Can I get you interested in joining the tautology club? $\endgroup$
    – Mindwin Remember Monica
    Commented Apr 26, 2017 at 15:36
  • 11
    $\begingroup$ @Mindwin Ah, but the amazing thing about these "Henkin sentences" is that they are not so trivial to prove. $\endgroup$
    – Gro-Tsen
    Commented Apr 26, 2017 at 15:50
  • 3
    $\begingroup$ This made my world that much bigger. Thank you. $\endgroup$
    – Akshat Mahajan
    Commented May 2, 2017 at 2:52
38
$\begingroup$

$AB-BA=I$ has no solution in finite matrices. Pf: Trace it!

Improve this answer
$\endgroup$
3
  • 21
    $\begingroup$ Except void matrices ($n=0$ :) $\endgroup$
    – Duchamp Gérard H. E.
    Commented May 15, 2017 at 0:04
  • 3
    $\begingroup$ $AB - BA= I$ not solvable in Banach algebras. Pf: Spectra of AB and BA. $\endgroup$
    – David Handelman
    Commented Apr 16, 2019 at 13:04
  • 12
    $\begingroup$ Except when the dimension is equal to zero in the coefficient ring (e.g. $M_{2 \times 2}(\mathbb{F}_2)$). $\endgroup$
    – WhatsUp
    Commented Apr 16, 2019 at 14:12
35
$\begingroup$

$n!$ divides $(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1})$.

Proof: $\mathfrak{S}_n$ embeds in $\mathrm{GL}_n(\mathbf{F}_2)$. $\quad \square$

(I have read this elegant justification on MO someday, yet I do not find it now.)

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ What does the fancy $\mathfrak{S}_n$ stand for, symmetric group on $n$ letters? $\endgroup$
    – Stefan Perko
    Commented Jun 7, 2018 at 14:24
  • 2
    $\begingroup$ @StefanPerko Absolutely! $\endgroup$
    – Desiderius Severus
    Commented Jun 7, 2018 at 14:49
  • 4
    $\begingroup$ Nice! But I think it should be $\operatorname{GL}_n(\mathbf{F}_2)$ rather than $\operatorname{GL}_2$. $\endgroup$
    – Zach Teitler
    Commented Jun 7, 2018 at 18:16
  • 1
    $\begingroup$ @ZachTeitler Thanks for the correction $\endgroup$
    – Desiderius Severus
    Commented Jun 8, 2018 at 7:58
  • 3
    $\begingroup$ @M.Winter Good question. It is $2^n-4$ (then $2^n-8$, and so on). The reason is that $|\operatorname{GL}_n(\mathbf{F}_2)| = (2^n-1)(2^n-2)(2^n-4)(2^n-8)\dotsm(2^n-2^{n-1})$. And the reason for that is that if you build an invertible matrix column by column, after choosing the first $k$ columns, the next column to be chosen out of the $2^n$ possible vectors must not lie in the span of the first $k$ columns, which is a $k$-dimensional subspace so it has $2^k$ elements, leaving $2^n-2^k$ choices for the $(k+1)$st column. $\endgroup$
    – Zach Teitler
    Commented Sep 1, 2020 at 21:55
31
$\begingroup$

Halting problem - there is no computer program which can determine if an arbitrary computer program halts on a specified input. Link

Improve this answer
$\endgroup$
29
$\begingroup$

You cannot comb a hairy ball, should you wish to.

Improve this answer
$\endgroup$
2
  • 11
    $\begingroup$ The wind always stands still somewhere. $\endgroup$
    – user1504
    Commented May 6, 2017 at 3:15
  • 4
    $\begingroup$ Hairy donuts on the other hand... $\endgroup$
    – David
    Commented Feb 24, 2019 at 4:16
19
$\begingroup$

Mihăilescu's theorem (ex Catalan conjecture) - $8$ and $9$ are the only consecutive proper powers of natural numbers. Link

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ first proved in 2002? WOW $\endgroup$
    – Forever Mozart
    Commented May 6, 2017 at 3:28
19
$\begingroup$

Sphere packing-The E8 lattice provides the optimal packing in eight-dimensional space. Link

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ Still within the twitter limit :) : Sphere packing-The E8 lattice provides the optimal packing in eight-dimensional space, Pf: LP+modular forms arxiv.org/abs/1603.04246 $\endgroup$
    – Gil Kalai
    Commented Apr 26, 2017 at 8:58
18
$\begingroup$

Borsuk's conjecture - a counterexample for DIM>2000, the tensor product of the unit sphere with itself. Link

Improve this answer
$\endgroup$
18
$\begingroup$

Wedderburn's theorem-Every finite skew field is a field. Pf: class equation on centralizers and cyclotomic irreducibility. Link

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Edited to give some idea on the "essence" of the proof. $\endgroup$
    – Francesco Polizzi
    Commented Apr 26, 2017 at 14:54
  • 6
    $\begingroup$ Alternative proof (not to be confused with "alt-proof"): apply Chevalley(-Warning) to the norm form. $\endgroup$
    – Noam D. Elkies
    Commented Apr 27, 2017 at 1:00
17
$\begingroup$

Turing discovers problems that even computers cannot solve. Link

Improve this answer
$\endgroup$
4
  • 38
    $\begingroup$ You won't believe the second, and the fifth blew my mind! $\endgroup$
    – Peter Samuelson
    Commented Apr 26, 2017 at 13:38
  • 2
    $\begingroup$ @PeterSamuelson I don't get it. Second what, fifth what? $\endgroup$
    – Todd Trimble
    Commented Apr 26, 2017 at 16:07
  • 13
    $\begingroup$ @Todd, it is an internetism, to get people to click on a link to a list of, oh, money saving incredible mathematical tweets? Gerhard "Using This One Weird Tip" Paseman, 2017.04.26. $\endgroup$
    – Gerhard Paseman
    Commented Apr 26, 2017 at 19:34
  • $\begingroup$ @GerhardPaseman Oh yes, I've seen that. Makes sense now. $\endgroup$
    – Todd Trimble
    Commented Apr 26, 2017 at 19:38
17
$\begingroup$

Breaking News: A mathematician blew up 6 points on a plane! You won't believe what happened next...

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ BREAKING NEWS: a plane got blown up by a mathematician. At least five cups of coffee are thought to be dead. $\endgroup$
    – Michael Freimann
    Commented Sep 21, 2018 at 19:15
16
$\begingroup$

One more:

CFSG - The largest sporadic simple group has order 808017424794512875886459904961710757005754368000000000.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Oops, that was two links, so it doesn't fit the conditions. Feel free to ignore either - the two Wikipedia pages have direct links to each other. $\endgroup$
    – GNiklasch
    Commented Apr 26, 2017 at 10:47
  • 5
    $\begingroup$ Is there any intrinsic definition of sporadic group? Out of curiosity, I'd like to know if any other finite simple group was once considered as sporadic (= not abelian, alternating, or in any "list" of Lie-flavor type) before it was extrapolated as Lie type. $\endgroup$
    – YCor
    Commented Mar 9, 2019 at 15:55
16
$\begingroup$

Cantor's theorem!

The cardinality of the reals is greater than that of the natural numbers.

Also, various incompleteness results along the lines of the Mathematical T-Rex:

The continuum hypothesis is neither provable nor disprovable from ZFC, unless ZFC is inconsistent to begin with!

(The above can be extended to include a myriad of choice-related statements and ZF, for example.)

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ You still have room to mention "diagonalization" and "forcing", respectively, if we are to focus on the "essence of a notable mathematical development" aspect. If you split "CH isn't provable..." and "CH isn't disprovable…" into two tweets, you could accommodate the constructible universe, too. $\endgroup$
    – GNiklasch
    Commented Apr 26, 2017 at 12:44
15
$\begingroup$

Of course, every finite group of odd order is solvable.

Improve this answer
$\endgroup$
4
  • 26
    $\begingroup$ I'd like to see the essence of this development on a tweet. :) $\endgroup$
    – Gil Kalai
    Commented Apr 26, 2017 at 12:33
  • 2
    $\begingroup$ I have discovered a truly remarkable proof of this theorem which this <s>margin</s>tweet is too small to contain. $\endgroup$
    – chx
    Commented Apr 30, 2017 at 0:35
  • 1
    $\begingroup$ Savage one .... $\endgroup$
    – DS R
    Commented May 7, 2017 at 14:28
  • 2
    $\begingroup$ Proof: Apply CFSG ;-) $\endgroup$
    – Zach Teitler
    Commented Sep 20, 2019 at 20:04
15
$\begingroup$

Invert 2×2 matrix A? Easy: switch diagonal entries, negate off-diags, & divide by Δ=det(A).
Pf: divide A²-tA+ΔI=0 by A, solve for 1/A !

MO link

Improve this answer
$\endgroup$
14
$\begingroup$

Lindemann's theorem - You need more than a compass and a ruler to square a circle. Link

Edit Or if we really want the essence of the argument, on which a whole lot of stronger results have been patterned since:

Exploiting the properties of the exponential function, if $\pi$ was algebraic there'd be rational integer strictly between 0 and 1.

Improve this answer
$\endgroup$
5
  • $\begingroup$ OK, I'll stop now… :) $\endgroup$
    – GNiklasch
    Commented Apr 26, 2017 at 9:37
  • $\begingroup$ Well, Lindemann's theorem is much more than this. "Lindemann's theorem: pi is transcendental" would be better. $\endgroup$
    – Francesco Polizzi
    Commented Apr 26, 2017 at 9:42
  • 2
    $\begingroup$ Sure. I intentionally toned it down so as to mean something to a broader audience, who might not want to expend the extra time to follow a link... $\endgroup$
    – GNiklasch
    Commented Apr 26, 2017 at 9:51
  • $\begingroup$ Lindemann's theorem does not say $\pi$ can be approximated too well by rationals to be algebraic. As far as we know, $\pi$ is not particularly well approximated by rationals. $\endgroup$
    – Robert Israel
    Commented Apr 26, 2017 at 15:23
  • $\begingroup$ Thank you @Robert Israel. Fixed the toned-up version (I hope). $\endgroup$
    – GNiklasch
    Commented Apr 26, 2017 at 15:33
14
$\begingroup$

One among $\pi+e$ and $\pi e$ is irrational. Proof: If not, then $(x+e)(x+\pi) \in \mathbb{Q}[x]$ and hence $e$ and $\pi$ would be algebraic.

NOTE: It is still open whether either of $\pi+e$ and $\pi e$ is irrational.

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ "One" meaning "at least one". $\endgroup$
    – Gerry Myerson
    Commented Apr 28, 2019 at 6:34
  • 6
    $\begingroup$ Yes, but that would get me over the 140 character limit. ;-) $\endgroup$
    – Santi Spadaro
    Commented Apr 28, 2019 at 8:09
  • 2
    $\begingroup$ It might be better to say that it is still open whether either of $\pi + e$ and $\pi e$ is rational. $\endgroup$
    – Zach Teitler
    Commented Mar 21, 2020 at 18:46
14
$\begingroup$

This is actually a real tweet by Ryan O'Donnell on Huang's proof of the sensitivity conjecture.

Hao Huang@Emory:

Ex.1: ∃edge-signing of n-cube with 2^{n-1} eigs each of +/-sqrt(n)

Interlacing=>Any induced subgraph with >2^{n-1} vtcs has max eig >= sqrt(n)

Ex.2: In subgraph, max eig <= max valency, even with signs

Hence [GL92] the Sensitivity Conj, s(f) >= sqrt(deg(f))

Improve this answer
$\endgroup$
1
1
2 3

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .