2 citations · 3 across the 8 of their papers we have counts for
8 papers · 1 filter
The largest -free set of vertices in a random graph
Tom Bohman, Marcus Michelen, Dhruv Mubayi
For and a graph , let be the maximum number of vertices in a -free subgraph of . We investigate the value when is the random graph $G…
Comparability of random permutations in the strong Bruhat order
Nicholas Christo, Marcus Michelen
The (strong) Bruhat order for permutations provides a partial ordering defined as follows: two permutations are comparable if one can be obtained from the other by a sequence of ad…
The random stable roommates problem typically has no solution
Byron Chin, Marcus Michelen
Assume that potential roommates each have an ordered preference of the others. A stable matching is a perfect matching of the roommates in which no two unmatched…
A polynomial improvement for the odd cycle-complete Ramsey numbers
Marcelo Campos, Matthew Jenssen, Marcus Michelen +2
We give a polynomial improvement to the cycle-complete Ramsey numbers \[ r(C_{\ell},K_k) \geq k^{1+1/(\ell- 2) + \varepsilon_{\ell} + o(1)}, \] for all fixed odd with $k…
A new lower bound for the Ramsey numbers
Marcelo Campos, Matthew Jenssen, Marcus Michelen +1
We prove a new lower bound for the off-diagonal Ramsey numbers, \[ R(3,k) \geq \bigg( \frac{1}{3}+ o(1) \bigg) \frac{k^2}{\log k }\, , \] thereby narrowing the gap between the uppe…
Realizability of hypergraphs and high-dimensional contingency tables with random degrees and marginals
Nicholas Christo, Marcus Michelen
A result of Deza, Levin, Meesum, and Onn shows that the problem of deciding if a given sequence is the degree sequence of a 3-uniform hypergraph is NP complete. We tackle this prob…