![](/files/happy5.png)
extremal combinatorics
Sidorenko's Conjecture ★★★
Author(s): Sidorenko
Conjecture For any bipartite graph
and graph
, the number of homomorphisms from
to
is at least
.
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \left(\frac{2|E(G)|}{|V(G)|^2}\right)^{|E(H)|}|V(G)|^{|V(H)|} $](/files/tex/a6c4d985a1ddfc6c35b74c9ae8e23d64f97d7781.png)
Keywords: density problems; extremal combinatorics; homomorphism
Turán Problem for $10$-Cycles in the Hypercube ★★
Author(s): Erdos
Problem Bound the extremal number of
in the hypercube.
![$ C_{10} $](/files/tex/11903dbe89daae659b28a8bead9b43cae2995c3d.png)
Keywords: cycles; extremal combinatorics; hypercube
Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube ★★
Problem Determine the smallest percolating set for the
-neighbour bootstrap process in the hypercube.
![$ 4 $](/files/tex/1f1498726bb4b7754ca36de46c0ccdd09136d115.png)
Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation
Saturated $k$-Sperner Systems of Minimum Size ★★
Author(s): Morrison; Noel; Scott
Question Does there exist a constant
and a function
such that if
, then every saturated
-Sperner system
has cardinality at least
?
![$ c>1/2 $](/files/tex/71b371b57345af0cbcfd2ffd78362b8988723a7d.png)
![$ n_0(k) $](/files/tex/77717a7ba8441af96e47411a5b9a5d4a913f3dba.png)
![$ |X|\geq n_0(k) $](/files/tex/e6c6b51d4e2df6fd85840bc289e38c981674e057.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ \mathcal{F}\subseteq \mathcal{P}(X) $](/files/tex/cb32025ab3209d1516fd6ea63a4d8eb206a81411.png)
![$ 2^{(1+o(1))ck} $](/files/tex/1564812bc34ed3ebd060debb561be85acfb45f10.png)
Keywords: antichain; extremal combinatorics; minimum saturation; saturation; Sperner system
![Syndicate content Syndicate content](/misc/feed.png)