Results: Combinatorics REGS 2011

This page summarizes results obtained on the problems presented in the Summer 2011 Combinatorics REGS program. Problems are numbered as on the REGS index page.

Game matching number (Dan Cranston, Bill Kinnersley, Suil O, Douglas West)
    $\circ$ On any graph $G$, the difference between $\alpha'_{g}(G)$ and $\hat\alpha'_{g}(G)$ is at most 1, and either parameter may be larger than the other. (This result was independently proved by Hehui Wu.)
    $\circ$ Max can always force a matching of size at least $\frac 23\alpha'(G)$, with equality for a disjoint union of 6-cycles. At the cost of an additive constant, one can take the join of $rC_6$ with $k$ isolated vertices to increase the minimum degree and connectivity. (However, Question 1 remains open.)
    $\circ$ Min can always enforce $\alpha'_g(G)\le (3/2)k+1$, where $k$ is the minimum size of a maximal matching, by playing edges from a small maximal matching until no more are available. The bound is sharp; equality holds for $kP_4$.
    $\circ$ Max can force a perfect matching on any graph $G$ having a perfect matching $M$ such that if $uv,wx\in M$, then $uw\in M$ implies $vx\in M$. A special case is that Max can force a perfect matching in the cartesian product of any graph with $K_{r,r}$.
    $\circ$ Max is not guaranteed to be able to force a perfect matching even when the graph is so dense that only $n/2$ edges are missing. For the complement of a matching with odd size (so $n\equiv 2\mod 4$), Min can mirror the play of Max to reduce $n$ by $4$ and leave two vertices unmatched at the end.
    $\circ$ When playing on a path or cycle, optimal play leaves about 1/7 of the vertices unmatched. Jennifer Wise and Elyse Yeager independently obtained the exact answer for $P_n$ for all congruence classes. Consider $n=7k+r$, where $0\le r\le 6$. When Max starts, optimal play leaves $k$ vertices uncovered when $r$ is even, $k+1$ vertices uncovered when $r$ is odd. When Min starts, optimal play gives the same answer as when Max starts except when $r\in\{4,6\}$, in which case Min can reduce the final matching size by $1$. Optimal strategies by both players chew at one end of the one remaining path having at least three vertices; Min takes the second edge from the end (isolating one vertex); Max takes the third edge (isolating one edge). Similar ideas apply to disjoint unions of paths. After the first move on a cycle, the remaining game is on a path.
    $\circ$ For trees in general, Max can always force a matching with size at least 3/4 of the matching number, with equality for "combs" whose number of vertices is divisible by 8.
    $\circ$ In an $r$-regular connected $n$-vertex graph with Min playing first, Max can force a matching of size at least $rn/(4r-3)$ (maybe one less if Max starts). For $r=3$, the lower bound is $n/3$, and there is an infinite family where the game matching number is about $n(\frac 13+\frac 1{18})$. However, for $r\ge5$ this bound is weaker than the lower bound of $(2/3)\alpha'(G)$ that Max can guarantee.
    $\circ$ The lower bound for $3$-regular graphs also follows from the statement that in the independence game on a connected $4$-regular $N$-vertex graph with Min moving first, Max can force an independent set with size at least $2N/9$.
$(p,q)$-splits of (0,1)-matrices
Mean size of subtrees of a tree (Gzergely Bálint, Douglas West)
$\circ$ Some ideas suggest that the conjectured form of the extremal trees may not be correct.
Edge-achromatic number of $K_n$
Cops locating a robber (James Carraher, Ilkyoo Choi, Michelle Delcourt, Lars Erickson) For the version in which the cop scans a vertex that returns the distance to the robber, and the robber is not prevented from moving to the previously scanned vertex, the winner was determined for several classes of graphs. Recall that the fractional power $G^{1/m}$ is the graph obtained from $G$ by replacing each edge with a path of length $m$ through new vertices.
    $\circ$ The cop wins on the graphs $K_n^{1/m}$ with $m\ge n$, $K_{n,n}^{1/m}$ with $m\gt n$, $K_{n,k}^{1/m}$ with $m\ge n\gt k$, and $(P_n\Box P_m)^{1/2}$.
    $\circ$ The robber wins on graphs with girth at most $5$ and on $C_6$. It is unknown whether the robber wins on all graphs with girth $6$.
    $\circ$ The cop wins on cycles of length at least $7$.
    $\circ$ It is conjectured that the robber wins on $K_n^{1/m}$ when $m\lt n$. For another conjecture, let $v_S$ be the vector of distances from a vertex $v$ to the vertices in a vertex subset $S$ of $G$. It is conjectured that the cop wins on $G^{1/(\mu(G)+1)}$ for any graph $G$, where $\mu(G)$ is the minimum size of a set $S$ of vertices in $G$ such that the vectors $v_S$ are distinct for all $v\in V(G)$.
Number of chains in width-2 posets (Elizabeth Kupin, Ben Reiniger, Derrick Stolee)
$\circ$ An algorithmic procedure was developed to count the chains in a poset of width $2$; it is tractable when the number of "crossing cover relations" between two chains that cover all the elements is small. This leads to computationally simple formulas for the number of chains in a class of posets having width $2$, given a few numerical parameters that define the poset. By generating formulas for small configurations and evaluating these formulas on many inputs, it was determined that every number number below 1,000,000 (1 million) can be represented as the number of chains in a poset of width $2$.
$k$-corners in subsets of $d$-dimensional grids (Stephen Hartke, Hong Liu, Kevin Milans, Derrick Stolee, Douglas West) Let $f_{k,d}(n)$ be the maximum size of a subset of the $d$-dimensional grid of side-length $n$ that contains no $k$-dimensional corner . Let $g_{k,d}(n)$ be the analogous maximum having no "axis-aligned" $k$-dimensional corner (note that $g_{k,d}(n)\ge f_{k,d}(n)$).
    $\circ$ $g_{k,d}(n)\le kn^{d-1}$.
    $\circ$ $g_{d,d}(n)\ge d(n-1)^{d-1}$.
    $\circ$ For $2\le k\lt d$, there is a constant $c_{k,d}$ such that $g_{k,d}(n)\ge c_{k,d}n^{d-1}+O(n^{d-2})$.
    $\circ$ $g_{2,3}(n)\ge 3\binom n2+1$. We have a strategy that we expect to succeed in proving that this is the exact answer. Meanwhile, a counting argument has shown that the leading term $3n^2/2$ is correct.
Chromatic number of tournaments
Track number of line graphs (James Carraher, Tim LeSaulnier, Kevin Milans, Derrick Stolee, Douglas West)
$\circ$ The track number of the line graph of an $n$-vertex graph is at most $O(\log n)$. More importantly, the track number of $L(K_n)$ grows with $n$. In particular, if $n$ exceeds the $t$-color $3$-uniform Ramsey number that forces a homogeneous set of size $10$, then the track number of $L(K_n)$ exceeds $t$ (proof). Thus the track number of $L(K_n)$ grows at least as quickly as the inverse of the tower function (i.e., like "log*($n$)"). Since line graphs have interval number $2$, this implies that the track number can be arbitrarily large when the interval number is $2$. A later technique slightly improves the bounds.
Visibility number of hypercubes (Hannah Kolb, Jennifer Wise, Douglas West)
$\circ$ A fairly complicated construction found by Kolb and Wise shows that the visibility number of the 7-dimensional cube is 2. This means that the lower bound of $\lceil(d+1)/4\rceil$ that results from Euler's Formula is the correct value for $d\le10$. Because the 3-dimensional cube is a bar visibility graph, $\lceil d/3\rceil$ is an immediate general upper bound.
Ranking and list ranking of graphs
    $\circ$ (Daniel McDonald) It was known easily that for the path $P_n$, the ranking number is $\lceil \lg(n+1)\rceil$, and for the cycle $C_n$ it is $1+\lceil\lg n\rceil$. In fact, for paths and for cycles, the list ranking number or "rank-choosability" is the same as the ranking number. That is, even when the available ranks are not the same at each vertex, still a ranking can be chosen from lists of this size. The proof proceeds by giving a more general sufficient condition for choosing a ranking from lists whose sizes may vary from vertex to vertex. Surprisingly, the order of the list sizes along the path (or cycle) does not matter in satisfying that condition.
    $\circ$ (Hong Liu, Sara Loeb, Michael Santana) In a biranking of $G$ every path joining vertices with the same label must have both a vertex with a larger label and a vertex with a smaller label. The biranking number $b(G)$ is known for paths, cycles, and graphs with diameter at most $2$. For the generalized theta graph $\Theta(\ell_1,\ldots,\ell_r)$ with paths of lengths $\ell_1,\ldots,\ell_r$ in nonincreasing order and $\ell_r\ge3$, the students showed that $\max\{r+3,b(C_{\ell_1+\ell_2})\}\le b(\Theta(\ell_1,\ldots,\ell_r))\le r+2+b(P_{\ell_1-3})$.
     For the $n$-by-$n$ grid, the biranking number is between $2n$ and $6n+c$, where $c$ is a constant. The problem is also being studied for hypercubes.
$t$-tone colorings (Dan Cranston, Jaehoon Kim, Bill Kinnersley)
    $\circ$ Always $\tau_t(G) \le (t^2 + t)\Delta(G)$. Hence for any fixed value of $\Delta(G)$, we have $\tau_t(G) \le c_1 t^2$, for some constant $c_1$. On the other hand, there are graphs such that $\tau_t(G) \ge c_2 t^2 / \lg t$, so the asymptotics of the general upper bound in terms of $\Delta(G)$ cannot be improved by much.
    $\circ$ If $G$ is subcubic, then $\tau_2(G) \le 8$; this confirms one part of a conjecture of Bickle and Phillips. On the other hand, the Heawood graph (cubic and bipartite) has $2$-tone chromatic number $7$, which refutes a different part of the same conjecture (that every cubic graph not containing $K_4$ or $K_4-e$ has a $2$-tone $6$-coloring).
    $\circ$ For any fixed $t$, there exist constants $c_1$ and $c_2$ such that if $T$ is a tree, then $c_1 \sqrt{\Delta(T)} \le \tau_t(T) \le c_2 \sqrt{\Delta(T)}$. (Noted earlier for $t\le 4$.)
    $\circ$ If $G$ is bipartite, then $\tau_2(G) \le 2\sqrt{2} \Delta(G)$. If $G$ is chordal, then $\tau_2(G)\le(1+\sqrt{6}/2) \Delta(G)$. By a different argument, if $G$ is chordal, then $\tau_2(G) \le (2 + o(1)) \Delta(G)$. [The $o(1)$ terms make the latter result inferior to the former when $\Delta(G)$ is small.]
Accessibility of the Fibonacci sequence
Symmetry dynamics
Coloring of tangency graphs of cuboids
Homothetic Ramsey problems on grids
Revolutionaries and spies, revisited
$\circ$ Greg Puleo showed that last year's bound of $\sigma(G)\le \gamma(G)\lfloor r/m\rfloor$ is sharp.
$\circ$ Ben Reiniger observed that the distance power $G^k$ of $G$ is at least as good for the spies as $G$ is, while $G\Box H$ is at least as good for the revolutionaries as the better of $G$ and $H$ (this may also be in the paper by Howard and Smyth).
Paintability (James Carraher, Sarah Loeb, Thomas Mahoney, Gregory Puleo, Donald Tsai, Douglas West)
    $\circ$ If a graph $G$ is $k$-degenerate, then $G$ is $(k+1)$-paintable. Corollaries include that outerplanar graphs are $3$-paintable and chordal graphs are chromatic-paintable.
    $\circ$ If $G$ is a claw-free perfect graph with $\omega(G) \leq3$, then $\chi(G)=\chi_{p}(G) = \omega(G)$. (The proof first shows that the conclusion holds for "elementary" graphs.)
    $\circ$ We give an explicit winning strategy for Remover to show that the complement of a matching is chromatic-paintable. (This was proved by Huang, Wong, and Zhu using the Combinatorial Nullstellensatz.)
    $\circ$ We have determined all 3-paint-critical graphs: Odd cycles, $K_{4,2}$, graphs consisting of two disjoint even cycles joined by a path (of length at least $0$), $\Theta_{2r,2s,2t}$ with $r\ge1$ and $s,t\ge2$, and $\Theta_{2r+1,2s+1,2t+1}$ with $r\ge0$ and $s,t\ge1$.
    $\circ$ If $G$ is $k$-paintable, then there exists $n_{0}$ such that if $n\geq n_{0}$, then $G\vee K_{n}$ is chromatic-paintable. Good bounds on $n_0$ may yield positive results toward the corrected version of Ohba's Conjecture for paintability.
    $\circ$ If $G$ is $k$-paintable and $|V(G)|\leq \frac{r}{r-1}k$, then the join of $G$ with $r$ isolated vertices is $(k+1)$-paintable. An immediate corollary is the chromatic-paintability of the complement of a matching and some other complete multipartite graphs.
    $\circ$ Erdős, Rubin, and Taylor proved that $K_{k,r}$ is $k$-choosable if and only if $r\lt k^k$. The same condition holds for $k$-paintability (except for $K_{2,3}$). D. Hoffman and P. Johnson prove that $K_{k+1,r}$ is $k$-choosable if and only if $r\lt k^k-(k-1)^k$. However, there is a winning strategy for Marker when $r$ is somewhat smaller, which yields a family of graphs with paintability equal to choosability plus $1$. For example, when $k=4$, we have $\chi_\ell(K_{5,r})=4$ if and only if $r\lt 175$. However, $\chi_p(K_{5,r})\gt4$ if $r\gt 164$.
     A crucial lemma gives a criterion for Marker to win from a game position on a complete $X,Y$-bigraph. If $|X|=L$ and $|Y|=R$, the numbers of erasers on the vertices of $X$ are $e_1-1,\ldots,e_L-1$, and each vertex in $Y$ has at least $L-1$ erasers, then Marker wins if and only if the number of vertices in $Y$ having exactly $L-1$ erasers is at least $\prod_{i=1}^L e_i$. The lemma leads to a function $F_n(e_1,\ldots,e_L)$ defined recursively as follows: If any $e_i$ is $0$, then the value is $0$. Otherwise, the value is the product of $L-n$ smallest entries plus the value of $F_n(e'_1,\ldots,e'_L)$, where the new arguments are obtained by subtracting $1$ from $n$ largest among $e_1,\ldots,e_L$. Finally, the graph $K_{k+1,r}$ is $k$-paintable only if $r\lt F_2(k,\ldots,k)$ (here $L=k+1$). For larger sets on the smaller side, $k$-paintability of $K_{k+j,r}$ requires $r\lt F_{j+1}(k,\ldots,k)$ (with $L=k+j$).
    $\circ$ The sum-choosability of $G$, written $\chi_{sc}(G)$, is the least $k$ such that $G$ is $f$-choosable for some function $f\colon\,V(G)\to\mathbb{N}$ with sum $k$. Similarly, the sum-paintability of $G$, written $\chi_{sp}(G)$, is the least $k$ such that Remover has a winning strategy with $f(v)-1$ erasers at each vertex $v$ for some $f$ with sum $k$. The upper bound of $|V(G)|+|E(G)|$ on $\chi_{sc}(G)$ holds also for sum-paintability. Graphs attaining the upper bound on sum-choosability or sum-paintability are sc-greedy or sp-greedy.
     There are graphs, such as $\Theta_{2,2,2t}$ with $t\gt 1$, that are sp-greedy but not sc-greedy (in particular, their sum-paintability is greater than their sum-choosability). For $\Theta_{2,2,2t}$, this follows because the graph is $2$-choosable (making its sum-choosability less than the greedy bound by $1$), but a lemma shows that adding an ear of length at least $3$ to an sp-greedy graph (such as $C_4$) yields an sp-greedy graph. (Adding a leaf also preserves sp-greediness, so trees are also sp-greedy.)
    $\circ$ Berliner, Bostelmann, Brualdi, and Deatt [2006] proved that $\chi_{sc}(K_{2,r})=2r+\min\{l+m\colon\, lm\gt r\}$. Thus $K_{2,r}$ is far from sc-greedy. Nevertheless, if each vertex in the large part has $1$ eraser, and the numbers of erasers on the vertices in the small part are $l-1$ and $m-1$, then Remover wins if $(l-1)(m-1)\gt r$. Thus $\chi_{sp}(K_{2,r})=\chi_{sc}(K_{2,r})$. Note that $\Theta(\ell_1,\ldots,\ell_n)$ consists of $K_{2,t}$ plus long ears if $t$ entries among $\ell_1,\ldots,\ell_n$ equal $2$. Thus $\chi_{sp}(\Theta(\ell_1,\ldots,\ell_n))$ = $\chi_{sp}(K_{2,t})+\sum_{i\colon\,\ell_i\gt 2}(2\ell_i-1)$.
Stack-sortability (Hannah Kolb, Beth Kupin, Dan McDonald)
Monochromatic empty triangles
Art Gallery problems (Lawrence Erickson, David Hannasch, Jennifer Wise, Elyse Yeager)
$\circ$ The upper bound of 3 on the number of colors of guards needed for staircase polygons was shown to be sharp.
Counting $k$-paths in transitive tournaments (Dan Cranston, Greg Puleo, Michael Santana)
$\circ$ A procedure was developed to generate a recurrence for fixed $k$, where $a_n$ is the number of sets of edges in the transitive tournament of order $n$ that decompose into $k$ paths from the source to the sink. For $k=3$, the recurrence is $a_n=8a_{n-1}-16a_{n-2}+10a_{n-3}$.
$\circ$ For $k=2$, the recurrence is $a_n=4a_{n-1}-2a_{n-2}$. A bijection was found from the family of sets of edges that decompose into two such paths to the family of generalized compositions of $n$ with $2^i-1$ different types of $i$ for each positive integer $i$ (proof).
Stable covert networks
List distinguishing number of graphs
Monosources vs. rainbow cycles (Bill Kinnersley, Elyse Yeager)
$\circ$ One cannot guarantee that every $r$-edge-coloring of a tournament has a monosource or a rainbow $r$-cycle. In the actual conjecture, the length of the rainbow cycle is not specified. Nevertheless, the conclusion of that conjecture (for $r\ge3$?) also fails if one edge is left uncolored.
Expectancy of $\sigma$ in $\tau$-avoiding permutations
Colorful paths in colored graphs (Beth Kupin)
$\circ$ Let $H$ be a $2$-regular graph with $n$ vertices. Form $G$ from $H+C_n$ by adding a matching from $V(H)$ to $V(C)$. Every such graph $G$ can be $3$-colored so that each vertex starts a colorful path.
$\circ$ Some graphs mentioned above are bipartite. The $3$-coloring guaranteed above gives more than the partial results of Akbari, Liaghat, and Nikzad on colorings with more than optimal colors (for this very small set of graphs).
Cycle-complete Ramsey numbers
Bijections for tableaux and reduced words
Coloring of fractional powers of graphs (Stephen Hartke, Hong Liu, Sarka Petricova)
$\circ$ The conjecture that $\chi(G^{m/n})=\omega(G^{m/n})$ for $1\le m\le n$ when $\Delta(G)\ge3$ is false, but all the counterexamples so far are fractional powers of $C_3\Box P_2$. For $\Delta(G)\ge5$, the conjecture holds when $m$ is even or $\frac32 m+1\le n\le 2m+1$. For $\Delta(G)=4$, the conjecture holds when $m$ is even or $\frac32 m+1\le n\le 2m-1$. When $\Delta(G)=3$, the conjecture holds when $m$ is even and $\frac32 m+1\le n\le 2m+1$ and $G$ is $3$-edge-colorable.
Games built on chip-firing (Dan Cranston, Ben Reiniger, Douglas West)
$\circ$ For the topple-win game, the first player wins on $K_n$ when $n$ is odd. It is conjectured that the first player also wins when $n$ is even; this was proved through $n=10$.
$\circ$ The optimal lengths of the Max-start and Min-start games are equal on trees, where moves don't matter, and they differ by 1 on all other connected graphs.
The upper matching conjecture
Universal words for subpermutations
$\circ$ There were some results here.
Extension of matchings to spanning cycles in hypercubes
Unimodality of the independent set sequence
Acyclic digraphs with many linear extensions (Lawrence Erickson, David Hannasch, Jennifer Wise, Elyse Yeager)
$\circ$ Among $n$-vertex posets with a fixed number of comparable pairs, the poset having the maximum number of linear extensions is a semiorder.
$\circ$ In some cases, it has also been shown that the extremal poset is bipartite. Within the bipartite semiorders, the group is looking for the posets with the most linear extensions.
Total weight choosability
Embedding planar Laman graphs on grids (Michelle Delcourt, Meghan Galiardi, Ben Reiniger, Jordan Tirrell)
$\circ$ The students are now studying the pagenumber of planar Laman graphs, conjecturing that they always embed on two pages. Relevant fact are a construction procedure for Laman graphs and a two-page embedding for trees relevant to any split of the vertices into initial portion and final portion along the line (due to S. Moran and Y. Wolfsthal [1993])
Precoloring list extension for planar graphs (Beth Kupin, Sarah Loeb, Thomas Mahoney, Sarka Petrickova)
$\circ$ Four configurations were found that could be obstructions to extending a coloring of seven outer vertices.
Game nonrepetitive coloring
Chromatic number of triangle-free graphs
The $\mathcal F$-saturation game and Game saturation number (James Carraher, Dan Cranston, Bill Kinnersley, Ben Reiniger, Douglas West)
    $\circ$ $\def\sat{{\rm sat}}$ Problem #1 on game matching number is the special case of game saturation number for $\mathcal{F}=\{P_3\}$.
    $\circ$ Every $K_{1,3}$-saturated subgraph of $K_n$ has $n$ or $n-1$ edges, so these are the only possibly outcomes of the game. The outcome is the even value in $\{n,n-1\}$ when Max starts, and it is the odd value when Min starts, except that for $n\in\{3,4,7\}$ the answer is $n$ no matter who starts, and for $n=2$ it is $1$.
    $\circ$ $\sat_g(K_n,P_4)$ is approximately $4n/5$, regardless of who starts.
    $\circ$ When $\mathcal F$ is the family of all $n$-vertex trees, $\sat_g(K_n,\mathcal F)=\binom{n-2}2+1$ for $n\ge6$.
    $\circ$ If $S_b$ denotes the graph obtained by subdividing one edge of a star with $b$ edges, then $\sat_g(S_b, 2K_2)=b$, while $\sat'_g(S_b, 2K_2)=2$. Thus the choice of the starting player may affect the value of the game by any amount.
    $\circ$ When $\mathcal F$ is the family of all odd cycles, $\sat_g(K_{2k}, \mathcal F)$ = $\sat'_g(K_{2k},\mathcal F)$ = $k^2$. This is a nontrivial instance where the choice of the starting player does not affect the value of the game. Also it is an instance where the value equals the maximum size of a $\mathcal F$-saturated subgraph.
    $\circ$ For the $P_4$-saturation game on $K_{m,n}$, the answer has been determined; it some cases the choice of who starts makes a significant difference. Assume $m\ge n$. There are some exceptions to the formulas when $n\le 2$. Otherwise, the value for the Max-start game is $n$ for even $n$, $m$ for odd $n$ when $m$ is even, and $m+(n-1)/2$ when both are odd. For the Min-start game, the value is $m+\lfloor n/2\rfloor$, except smaller by $1$ when $m$ is even and $n$ is odd.
The Equal Union Property (Jane Butterfield, Ilkyoo Choi, Stephen Hartke, Jaehoon Kim, Hannah Kolb, Beth Kupin, Amelia Tebbe, Douglas West) In generalizing to more than two families, a hypergraph graph satisfies the $t$-EUP if it has $t$ pairwise disjoint families of edges such that each has the same union. It satisfies the weak $t$-EMP if it has $t$ families (not necessarily disjoint) with this property. It satisfies the $t$-EMP if it has $t$ pairwise disjoint families such that any two cover each vertex the same number of times. It satisfies the weak $t$-EMP if it has $t$ families (not necessarily disjoint) with this property. The first results concern the case $t=2$.
    $\circ$ A 2-uniform hypergraph (a graph) satisfies the 2-EUP if and only if it contains an even cycle or a component containing two odd cycles. The maximum number of edges in a graph without this property is $n$.
    $\circ$ A 2-uniform hypergraph (a graph) satisfies the 2-EMP if and only if it contains a closed trail of even length. The maximum number of edges in a graph without this property is $\lfloor 4n/3\rfloor-1$.
    $\circ$ Lindstrom [1971] proved that the maximum number of edges in an $n$-vertex hypergraph not satisfying the $t$-EUP is $n(t-1)$. However, the maximum number of edges in an $n$-vertex hypergraph not satisfying the weak-$t$-EUP is less than $n+\lg t$.
    $\circ$ Every graph with more than $\lfloor 4n/3\rfloor$ edges satisfies the weak-$3$-EMP, and this is sharp.
    $\circ$ Every graph $G$ with more than $4(t-1)n$ edges satisfies the $t$-EMP. Brief sketch: There is a bipartite subgraph $H$ with more than $(p-1)n$ edges, where $p$ is a prime between $t$ and $2t$. A result of Alon, Friedland, and Kalai [1984] now shows that $H$ has a nontrivial subgraph in which every vertex degree is divisible by $p$. Such a bipartite graph has the $p$-EMP, which implies that it also has the $t$-EMP.
    $\circ$ Every $n$-vertex hypergraph with maximum edge size $k$ and at least $(\lg k+c_k\lg\lg k)n$ edges satisfies the $2$-EMP, for some $c_k$ such that $c_k\rightarrow 1$. A lower bound on the number of edges needed to force the $2$-EMP is $4n/3-n/(k+2)$. For $k=3$, the lower bound is $13n/9+O(1)$.
    $\circ$ With no restriction on the size of edges, every $n$-vertex hypergraph with at least $(\lg n+c_n\lg\lg n)n$ edges satisfies the $2$-EMP, for some $c_n$ such that $c_n\rightarrow 1$. (Again, adding $\lg t$ more edges forces the weak-$t$-EMP.
    $\circ$ A $t$-$\Delta$-system is a hypergraph with $t$ edges such that each contains a central set $S$ and outside $S$ the edges are pairwise disjoint; that is, the intersection of any two edges is $S$ (the structure generalizes stars in graphs). A hypergraph containing a $t$-$\Delta$-system satisfies the $t$-EMP. Erdős and Rado (and later Kostochka) gave upper bounds on the number of edges in an $n$-vertex hypergraph not containing a $t$-$\Delta$-system.
     In particular, when $t\ge3$, the $t$-EMP is forced by $(4+\epsilon)n^2 \left(\frac{\lg n}{\lg\lg\lg n}\right)^2$ edges when $n$ is sufficiently large in terms of $t$ and $\epsilon$. For hypergraphs with bounded edge size, the bound can be reduced roughly by a factor of $4$. If the Erdő-Rado conjecture that $2^{cn}$ edges (for some constant $c$ less than $1$) force a $t$-$\Delta$-system in an $n$-vertex hypergraph is true, then the upper bounds on the number of edges to force the $t$-EMP become linear.
Equivalence coverings of cycle-powers
MST for point-sets in the unit square
$\circ$ There were some observations here.
Concavity of mixed van der Waerden numbers
Arrangements of n lines in the plane

Properties of co-spectral graphs
Extensions of biclique decomposition