More Like this

1. Dynamics of plane partitions: Proof of the Cameron–Fon-Der-Flaass conjecture

   https://doi.org/10.1017/fms.2020.61  

   Patrias, Rebecca; Pechenik, Oliver (January 2020, Forum of Mathematics, Sigma)

   null (Ed.)

   Abstract One of the oldest outstanding problems in dynamical algebraic combinatorics is the following conjecture of P. Cameron and D. Fon-Der-Flaass (1995): consider a plane partition P in an $$a \times b \times c$$ box $${\sf B}$$ . Let $$\Psi (P)$$ denote the smallest plane partition containing the minimal elements of $${\sf B} - P$$ . Then if $p= a+b+c-1$ is prime, Cameron and Fon-Der-Flaass conjectured that the cardinality of the $$\Psi $$ -orbit of P is always a multiple of p . This conjecture was established for $$p \gg 0$$ by Cameron and Fon-Der-Flaass (1995) and for slightly smaller values of p in work of K. Dilks, J. Striker and the second author (2017). Our main theorem specializes to prove this conjecture in full generality. 

   more » « less
2. Pure Pairs. V. Excluding Some Long Subdivision

   https://doi.org/10.1007/s00493-023-00025-8  

   Scott, Alex; Seymour, Paul; Spirkl, Sophie (June 2023, Combinatorica)

   A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε>0, there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with |A|,|B|≥εn. He also proved that for all c>0 there exists ε>0 such that for every comparability graph G with n>1 vertices, there is a pure pair A, B with |A|,|B|≥εn1−c; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c>0, and all ℓ1,ℓ2≥4/c+9, there exists ε>0 such that, if G is an (n>1)-vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2, then there is a pure pair A, B in G with |A|≥εn and |B|≥εn1−c. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph. 

   more » « less
3. The Computational Power of Discrete Chemical Reaction Networks with Bounded Executions

   https://doi.org/10.4230/LIPIcs.DISC.2024.20  

   Doty, David; Heckmann, Ben (October 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Alistarh, Dan (Ed.)

   Chemical reaction networks (CRNs) model systems where molecules interact according to a finite set of reactions such as A + B → C, representing that if a molecule of A and B collide, they disappear and a molecule of C is produced. CRNs can compute Boolean-valued predicates ϕ:ℕ^d → {0,1} and integer-valued functions f:ℕ^d → ℕ; for instance X₁ + X₂ → Y computes the function min(x₁,x₂), since starting with x_i copies of X_i, eventually min(x₁,x₂) copies of Y are produced. We study the computational power of execution bounded CRNs, in which only a finite number of reactions can occur from the initial configuration (e.g., ruling out reversible reactions such as A ⇌ B). The power and composability of such CRNs depend crucially on some other modeling choices that do not affect the computational power of CRNs with unbounded executions, namely whether an initial leader is present, and whether (for predicates) all species are required to "vote" for the Boolean output. If the CRN starts with an initial leader, and can allow only the leader to vote, then all semilinear predicates and functions can be stably computed in O(n log n) parallel time by execution bounded CRNs. However, if no initial leader is allowed, all species vote, and the CRN is "non-collapsing" (does not shrink from initially large to final O(1) size configurations), then execution bounded CRNs are severely limited, able to compute only eventually constant predicates. A key tool is a characterization of execution bounded CRNs as precisely those with a nonnegative linear potential function that is strictly decreased by every reaction [Czerner et al., 2024]. 

   more » « less
4. A periodic isoperimetric problem related to the unique games conjecture

   https://doi.org/10.1002/rsa.20877  

   Heilman, Steven (July 2019, Random Structures & Algorithms)

   We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Letn ≥ 2. Suppose a subset Ω ofn‐dimensional Euclidean spacesatisfies −Ω = Ω^cand Ω + v = Ω^c(up to measure zero sets) for every standard basis vector. For anyand for anyq ≥ 1, letand let. For anyx ∈ ∂Ω, letN(x) denote the exterior normal vector atxsuch that ‖N(x)‖₂ = 1. Let. Our main result shows thatBhas the smallest Gaussian surface area among all such subsets Ω, less a small error:In particular,Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10⁻⁹would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture. 

   more » « less
5. Cops and Robbers on P5-Free Graphs

   https://doi.org/10.1137/23M1549912  

   Chudnovsky, Maria; Norin, Sergey; Seymour, Paul D; Turcotte, Jérémie (March 2024, SIAM Journal on Discrete Mathematics)

   We prove that every connected P5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5-free graph G with independence number at least three contains a three-vertex induced path with vertices a-b-c in order, such that every neighbor of c is also adjacent to one of a,b. 

   more » « less