diff options
Diffstat (limited to 'data/papers.bib')
| -rw-r--r-- | data/papers.bib | 251 |
1 files changed, 163 insertions, 88 deletions
diff --git a/data/papers.bib b/data/papers.bib index fa1037a..aa2e186 100644 --- a/data/papers.bib +++ b/data/papers.bib @@ -1,3 +1,16 @@ +@unpublished{briggs_vietoris, + title = {Facets in the Vietoris–Rips complexes of hypercubes}, + author = {Briggs, Joseph and Feng, Ziqin}, + month = {mar}, + year = {2025}, + eprint = {2408.01288}, + eprinttype = {arXiv}, + eprintclass = {math.AT}, + journal = {Experimental Mathematics}, + doi = {10.1080/10586458.2025.2474034}, + abstract = {In this paper, we investigate the facets of the Vietoris–Rips complex $\mathcal{VR}(Q_n; r)$ where $Q_n$ denotes the $n$-dimensional hypercube. We are particularly interested in those facets which are somehow independent of the dimension $n$. Using Hadamard matrices, we prove that the number of different dimensions of such facets is a super-polynomial function of the scale $r$, assuming that $n$ is sufficiently large. We show also that the $(2r-1)$-th dimensional homology of the complex $\mathcal{VR}(Q_n; r)$ is non-trivial when $n$ is large enough, provided that the Hadamard matrix of order $2r$ exists.}, +} + @unpublished{briggs_frogs, title = {Frogs, hats and common subsequences}, author = {Briggs, Joseph and Parker, Alex and Schwieder, Coy}, @@ -6,100 +19,93 @@ eprint = {2404.07285}, eprinttype = {arXiv}, eprintclass = {math.CO}, - keywords = {submitted}, + journal = {Electronic Journal of Probability}, + abstract = {Write $W^{(n)}$ to mean the $n$-letter word obtained by repeating a fixed word $W$ and let $R_n$ denote a uniformly random $n$-letter word sampled from the same alphabet as $W$. We are interested in the average length of the longest common subsequence between $W^{(n)}$ and $R_n$, which is known to be $\gamma(W)\cdot n+o(n)$ for some constant $\gamma(W)$. Bukh and Cox recently developed an interacting particle system, dubbed the frog dynamics, which can be used to compute the constant $\gamma(W)$ for any fixed word $W$. They successfully analyzed the simplest case of the frog dynamics to find an explicit formula for the constants $\gamma(12\cdots k)$. We continue this study by using the frog dynamics to find an explicit formula for the constants $\gamma(12\cdots kk\cdots 21)$. The frog dynamics in this case is a variation of the PushTASEP on the ring where some clocks are identical. Interestingly, exclusion processes with correlated clocks of this type appear to have not been analyzed before. Our analysis leads to a seemingly new combinatorial object which could be of independent interest: frogs with hats!}, } + @unpublished{briggs_phases, author = {Briggs, Joseph}, title = {Phase transitions in isoperimetric problems on the integers}, year = {2024}, month = {feb}, + url = {https://arxiv.org/abs/2307.00116}, eprint = {2402.14087}, eprintclass = {math.CO}, eprinttype = {arxiv}, - keywords = {accepted}, - journal = {Discrete Mathematics} -} - -@article{briggs_vietoris, - author = {Briggs, Joseph and Feng, Ziqin}, - doi = {10.1080/10586458.2025.2474034}, - journal = {Experimental Mathematics}, - month = {mar}, - pages = {1--9}, - publisher = {Informa UK Limited}, - title = {Facets in the {V}ietoris\textendash{}{R}ips Complexes of Hypercubes}, - year = {2025}, - keywords = {published}, - eprint = {2408.01288}, - eprinttype = {arXiv}, - eprintclass = {math.AT}, + journal = {Discrete Mathematics}, + abstract = {Barber and Erde asked the following question: if $B$ generates $\mathbb Z^n$ as an additive group, then must the extremal sets for the vertex/edge-isoperimetric inequality on the Cayley graph $\operatorname{Cay}(\mathbb Z^n,B)$ form a nested family? We answer this question negatively for both the vertex- and edge-isoperimetric inequalities, specifically in the case of $n=1$. The key is to show that the structure of the cylinder $\mathbb Z\times(\mathbb Z/k\mathbb Z)$ can be mimicked in certain Cayley graphs on $\mathbb Z$, leading to a phase transition. We do, however, show that Barber–Erde's question for Cayley graphs on $\mathbb Z$ has a positive answer if one is allowed to ignore finitely many sets.} } -@article{heath_oddcycles, +@unpublished{heath_oddcycles, author = {Heath, Emily and Martin, Ryan R.}, - doi = {10.1002/jgt.23197}, - journal = {Journal of Graph Theory}, - month = {apr}, - pages = {745--780}, - publisher = {Wiley}, title = {The maximum number of odd cycles in a planar graph}, - volume = {108}, year = {2025}, - keywords = {published}, + month = {apr}, + url = {https://arxiv.org/abs/2307.00116}, eprint = {2307.00116}, eprintclass = {math.CO}, eprinttype = {arxiv}, - % issue = {4}, + journal = {Journal of Graph Theory}, + doi = {10.1002/jgt.23197}, + abstract = {How many copies of a fixed odd cycle, $C_{2m+1}$, can a planar graph contain? We answer this question asymptotically for $m\in\{2,3,4\}$ and prove a bound which is tight up to a factor of $3/2$ for all other values of $m$. This extends the prior results of Cox–Martin and Lv et al. on the analogous question for even cycles. Our bounds result from a reduction to the following maximum likelihood question: which probability mass $\mu$ on the edges of some clique maximizes the probability that $m$ edges sampled independently from $\mu$ form either a cycle or a path?} } @article{sipp, - author = {Brennan, Zach and Curtis, Bryan and Gomez-Leos, Enrique and Hadaway, Kimberly and Hogben, Leslie and Thompson, Conor}, + author = {Brennan, Zachary and Curtis, Bryan and Gomez-Leos, Enrique and Hadaway, Kimberly and Hogben, Leslie and Thompson, Conor}, title = {Orthogonal realizations of random sign patterns and other applications of the SIPP}, - journal = {Electronic Journal of Linear Algebra}, - volume = {39}, - pages = {434--459}, year = {2023}, month = {aug}, - doi = {10.13001/ela.2023.7579}, + url = {https://journals.uwyo.edu/index.php/ela/article/view/7579}, eprint = {2212.05207}, eprintclass = {math.CO}, eprinttype = {arxiv}, + doi = {10.13001/ela.2023.7579}, keywords = {published}, - author+an = {1=earlygrad; 3=earlygrad; 4=earlygrad; 6=earlygrad}, - abstract = {A sign pattern is an array with entries in $\{+,-,0\}$. A matrix $Q$ is row orthogonal if $QQ^T = I$. The Strong Inner Product Property (SIPP), introduced in [B.A.~Curtis and B.L.~Shader, Sign patterns of orthogonal matrices and the strong inner product property, Linear Algebra Appl. 592: 228--259, 2020], is an important tool when determining whether a sign pattern allows row orthogonality because it guarantees there is a nearby matrix with the same property, allowing zero entries to be perturbed to nonzero entries, while preserving the sign of every nonzero entry. This paper uses the SIPP to initiate the study of conditions under which random sign patterns allow row orthogonality with high probability. Building on prior work, $5\times n$ nowhere zero sign patterns that minimally allow orthogonality are determined. Conditions on zero entries in a sign pattern are established that guarantee any row orthogonal matrix with such a sign pattern has the SIPP.} + journal = {Electronic Journal of Linear Algebra}, + abstract = {A sign pattern is an array with entries in $\{+,-,0\}$. A matrix $Q$ is row orthogonal if $QQ^T = I$. The Strong Inner Product Property (SIPP), introduced in [B.A.~Curtis and B.L.~Shader, Sign patterns of orthogonal matrices and the strong inner product property, Linear Algebra Appl. 592: 228–259, 2020], is an important tool when determining whether a sign pattern allows row orthogonality because it guarantees there is a nearby matrix with the same property, allowing zero entries to be perturbed to nonzero entries, while preserving the sign of every nonzero entry. This paper uses the SIPP to initiate the study of conditions under which random sign patterns allow row orthogonality with high probability. Building on prior work, $5\times n$ nowhere zero sign patterns that minimally allow orthogonality are determined. Conditions on zero entries in a sign pattern are established that guarantee any row orthogonal matrix with such a sign pattern has the SIPP.} } -@article{cox_planarcycles, - author = {Martin, Ryan R.}, - title = {The maximum number of 10- and 12-cycles in a planar graph}, - year = {2023}, - month = {feb}, - eprint = {2106.02966}, - eprinttype = {arxiv}, +@article{unicorns, + author = {King, Emily J. and Mixon, Dustin G. and Parshall, Hans}, + title = {Uniquely optimal codes of low complexity are symmetric}, + year = {2020}, + month = {aug}, + url = {http://arxiv.org/abs/2008.12871}, + eprint = {2008.12871}, eprintclass = {math.CO}, - journal = {Discrete Mathematics}, - volume = {346}, - number = {2}, - pages = {113245}, + eprinttype = {arxiv}, + journal = {Journal of Experimental Mathematics}, + keywords = {accepted}, + abstract = {We formulate explicit predictions concerning the symmetry of optimal codes in compact metric spaces. This motivates the study of optimal codes in various spaces where these predictions can be tested.} +} + +@article{cox_planarcycles, + author = {Cox, Christopher and Martin, Ryan R.}, + title = {The maximum number of 10- and 12-cycles in a planar graph}, + year = {2023}, + month = {feb}, + url = {https://www.sciencedirect.com/science/article/pii/S0012365X22004514}, + eprint = {2106.02966}, + eprinttype = {arxiv}, + eprintclass = {math.CO}, + journal = {Discrete Mathematics}, doi = {10.1016/j.disc.2022.113245}, - keywords = {published}, + abstract = {For a fixed planar graph $H$, let $\operatorname{\mathbf{N}}_{\mathcal{P}}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In the case when $H$ is a cycle, the asymptotic value of $\operatorname{\mathbf{N}}_{\mathcal{P}}(n,C_m)$ is currently known for $m\in\{3,4,5,6,8\}$. In this note, we extend this list by establishing $\operatorname{\mathbf{N}}_{\mathcal{P}}(n,C_{10})\sim(n/5)^5$ and $\operatorname{\mathbf{N}}_{\mathcal{P}}(n,C_{12})\sim(n/6)^6$. We prove this by answering the following question for $m\in\{5,6\}$, which is interesting in its own right: which probability mass $\mu$ on the edges of some clique maximizes the probability that $m$ independent samples from $\mu$ form an $m$-cycle?}, } @article{cox_planarpaths, - author = {Martin, Ryan R.}, - title = {Counting paths, cycles and blow-ups in planar graphs}, - journal = {Journal of Graph Theory}, - volume = {101}, - number = {3}, - pages = {521-558}, - year = {2022}, - month = {apr}, + author = {Martin, Ryan R.}, + title = {Counting paths, cycles and blow-ups in planar graphs}, + year = {2022}, + month = {apr}, + journal = {Journal of Graph Theory}, + url = {https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.22838}, + eprint = {2101.05911}, + eprinttype = {arxiv}, + eprintclass = {math.CO}, doi = {10.1002/jgt.22838}, - eprint = {2101.05911}, - eprinttype = {arxiv}, - eprintclass = {math.CO}, - keywords = {published}, + abstract = {For a planar graph $H$, let $\operatorname{\mathbf{N}}_{\mathcal P}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In this paper, we prove that $\operatorname{\mathbf{N}}_{\mathcal P}(n,P_7)\sim{4\over 27}n^4$, $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_6)\sim(n/3)^3$, $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_8)\sim(n/4)^4$ and $\operatorname{\mathbf{N}}_{\mathcal P}(n,K_4\{1\})\sim(n/6)^6$, where $K_4\{1\}$ is the $1$-subdivision of $K_4$. In addition, we obtain significantly improved upper bounds on $\operatorname{\mathbf{N}}_{\mathcal P}(n,P_{2m+1})$ and $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_{2m})$ for $m\geq 4$. For a wide class of graphs $H$, the key technique developed in this paper allows us to bound $\operatorname{\mathbf{N}}_{\mathcal P}(n,H)$ in terms of an optimization problem over weighted graphs.}, } @article{lcsfrogs, @@ -108,32 +114,44 @@ year = {2022}, month = {apr}, journal = {Annals of Applied Probability}, - volume = {32}, - number = {2}, - pages = {1295--1332}, - doi = {10.1214/21-AAP1709}, + url = {https://projecteuclid.org/journals/annals-of-applied-probability/volume-32/issue-2/Periodic-words-common-subsequences-and-frogs/10.1214/21-AAP1709.short}, + date = {2019-12-07T14:30:46Z}, eprint = {1912.03510}, eprintclass = {math.PR}, eprinttype = {arxiv}, + doi = {10.1214/21-AAP1709}, + urldate = {2019-12-17T16:26:03.191683Z}, extra = {Code}, + extraurl = {http://www.borisbukh.org/code/lcsfrogs19.html}, keywords = {published}, + abstract = {Let $W^{(n)}$ be the $n$-letter word obtained by repeating a fixed word $W$, and let $R_n$ be a random $n$-letter word over the same alphabet. + We show several results on the length of longest common subsequence (LCS) between $W^{(n)}$ and $R_n$; in particular, we show that its expectation is $\gamma_W n-O(\sqrt{n})$ for an efficiently-computable constant $\gamma_W$. + <br /> + This is done by relating the problem to a new interacting particle system, which we dub ``frog dynamics''. + In this system, the particles (`frogs') hop over one another in the order given by their labels. + Stripped of the labeling, the frog dynamics reduces to a variant of the PushTASEP. + <br /> + In the special case when all symbols of $W$ are distinct, we obtain an explicit formula for the constant $\gamma_W$ and a closed-form expression for the stationary distribution of the associated frog dynamics. + <br /> + In addition, we propose new conjectures about the asymptotic of the LCS of a pair of random words. + These conjectures are informed by computer experiments using a new heuristic algorithm to compute the LCS. + Through our computations, we found periodic words that are more random-like than a random word, as measured by the LCS. + } } @article{cox_editdistance, - author = {Martin, Ryan R. and McGinnis, Daniel}, - title = {Accumulation points of the edit distance function}, - year = {2022}, - month = {jul}, - journal = {Discrete Mathematics}, - volume = {345}, - number = {7}, - pages = {112857}, - eprint = {2107.06706}, - eprinttype = {arxiv}, - eprintclass = {math.CO}, + author = {Martin, Ryan R. and McGinnis, Daniel}, + title = {Accumulation points of the edit distance function}, + year = {2022}, + month = {jul}, + journal = {Discrete Mathematics}, + eprint = {2107.06706}, + eprinttype = {arxiv}, + eprintclass = {math.CO}, + keywords = {published}, doi = {10.1016/j.disc.2022.112857}, - keywords = {published}, - author+an = {2=earlygrad}, + url = {https://www.sciencedirect.com/science/article/pii/S0012365X22000632}, + abstract = {Given a hereditary property $\mathcal H$ of graphs and some $p\in[0,1]$, the edit distance function $\operatorname{ed}_{\mathcal H}(p)$ is (asymptotically) the maximum proportion of "edits" (edge-additions plus edge-deletions) necessary to transform any graph of density $p$ into a member of $\mathcal H$. For any fixed $p\in[0,1]$, $\operatorname{ed}_{\mathcal H}(p)$ can be computed from an object known as a colored regularity graph (CRG). This paper is concerned with those points $p\in[0,1]$ for which infinitely many CRGs are required to compute $\operatorname{ed}_{\mathcal H}$ on any open interval containing $p$; such a $p$ is called an accumulation point. We show that, as expected, $p=0$ and $p=1$ are indeed accumulation points for some hereditary properties; we additionally determine the slope of $\operatorname{ed}_{\mathcal H}$ at these two extreme points. Unexpectedly, we construct a hereditary property with an accumulation point at $p=1/4$. Finally, we derive a significant structural property about those CRGs which occur at accumulation points.}, } @@ -143,6 +161,7 @@ journal = {Electronic Journal of Combinatorics}, year = {2020}, month = {sep}, + url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i3p49}, eprint = {1904.00246}, eprintclass = {math.CO}, eprinttype = {arxiv}, @@ -168,15 +187,25 @@ number = {1}, pages = {359--388}, doi = {10.1007/s11856-020-2027-7}, + url = {https://link.springer.com/article/10.1007%2Fs11856-020-2027-7}, eprint = {1803.02949}, eprinttype = {arxiv}, eprintclass = {math.CO}, keywords = {published}, + abstract = {How can $d+k$ vectors in $\mathbb{R}^d$ be arranged so that they are as close to orthogonal as possible? + In particular, define $\theta(d,k):=\min_X\max_{x\neq y\in X}|\langle x,y\rangle|$ where the minimum is taken over all collections of $d+k$ unit vectors $X\subseteq\mathbb{R}^d$. + In this paper, we focus on the case where $k$ is fixed and $d\to\infty$. + In establishing bounds on $\theta(d,k)$, we find an intimate connection to the existence of systems of ${k+1\choose 2}$ equiangular lines in $\mathbb{R}^k$. + Using this connection, we are able to pin down $\theta(d,k)$ whenever $k\in\{1,2,3,7,23\}$ and establish asymptotics for general $k$. + The main tool is an upper bound on $\mathbb{E}_{x,y\sim\mu}|\langle x,y\rangle|$ whenever $\mu$ is an isotropic probability mass on $\mathbb{R}^k$, which may be of independent interest. + Our results translate naturally to the analogous question in $\mathbb{C}^d$. + In this case, the question relates to the existence of systems of $k^2$ equiangular lines in $\mathbb{C}^k$, also known as SIC-POVM in physics literature. + } } @article{invturan, author = {Briggs, Joseph}, - title = {Inverting the Tur{\'a}n problem}, + title = {Inverting the Turán problem}, journal = {Discrete Mathematics}, publisher = {Elsevier BV}, year = {2019}, @@ -184,11 +213,18 @@ number = {7}, volume = {342}, pages = {1865--1884}, + url = {https://www.sciencedirect.com/science/article/abs/pii/S0012365X1930086X}, doi = {10.1016/j.disc.2019.03.005}, eprint = {1711.02082}, eprinttype = {arxiv}, - eprintclass = {math.CO}, + eprintclass = {math.CO}, + extra = {Supplementary materials}, keywords = {published}, + abstract = {Classical questions in extremal graph theory concern the asymptotics of $\operatorname{ex}(G,\mathcal{H})$ where $\mathcal{H}$ is a fixed family of graphs and $G=G_n$ is taken from a ``standard'' increasing sequence of host graphs $(G_1, G_2, \dots)$, most often $K_n$ or $K_{n,n}$. + Inverting the question, we can instead ask how large $e(G)$ can be with respect to $\operatorname{ex}(G,\mathcal{H})$. + We show that the standard sequences indeed maximize $e(G)$ for some choices of $\mathcal{H}$, but not for others. + Many interesting questions and previous results arise very naturally in this context, which also, unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs. + } } @article{frachaemers, @@ -201,11 +237,17 @@ number = {6}, volume = {65}, pages = {3340--3348}, + url = {https://ieeexplore.ieee.org/abstract/document/8585033}, doi = {10.1109/tit.2018.2889108}, eprint = {1802.00476}, eprinttype = {arxiv}, - eprintclass = {cs.IT}, + eprintclass = {math.IT}, keywords = {published}, + abstract = {In this note, we present a fractional version of Haemers' bound on the Shannon capacity of a graph, which is originally due to Blasiak. + This bound is a common strengthening of both Haemers' bound and the fractional chromatic number of a graph. + We show that this fractional version outperforms any bound on the Shannon capacity that could be attained through Haemers' bound. + We show also that this bound is multiplicative, unlike Haemers' bound. + } } @@ -219,16 +261,24 @@ number = {3}, volume = {35}, pages = {557--579}, + url = {https://link.springer.com/article/10.1007/s11083-017-9449-9}, doi = {10.1007/s11083-017-9449-9}, eprint = {1512.05261}, eprinttype = {arxiv}, - eprintclass = {math.CO}, + eprintclass = {math.CO}, + extra = {Code}, keywords = {published}, + abstract = {We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. + This is a natural extension of the ordered Ramsey numbers. + We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. + We explore connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice. + We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains. + } } @article{42choose, - author = {Berikkyzy, Zhanar and Dairyko, Michael and Hogenson, Kirsten and Kumbhat, Mohit and Lidick{\'y}, Bernard and Messerschmidt, Kacy and Moss, Kevin and Nowak, Kathleen and Palmowski, Kevin and Stolee, Derrick}, + author = {Berikkyzy, Zhanar and Dairyko, Michael and Hogenson, Kirsten and Kumbhat, Mohit and Lidicky, Bernard and Messerschmidt, Kacy and Moss, Kevin and Nowak, Kathleen and Palmowski, Kevin and Stolee, Derrick}, title = {(4,2)-choosability of planar graphs with forbidden structures}, journal = {Graphs and Combinatorics}, publisher = {Springer Nature}, @@ -237,10 +287,11 @@ number = {4}, volume = {33}, pages = {751--787}, + url = {https://link.springer.com/article/10.1007/s00373-017-1812-5}, doi = {10.1007/s00373-017-1812-5}, eprint = {1512.03787}, eprinttype = {arxiv}, - eprintclass = {math.CO}, + eprintclass = {math.CO}, keywords = {published}, abstract = {All planar graphs are $4$-colorable and $5$-choosable, while some planar graphs are not $4$-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. @@ -265,12 +316,16 @@ number = {4}, volume = {10}, pages = {691--705}, + url = {https://msp.org/involve/2017/10-4/p10.xhtml}, doi = {10.2140/involve.2017.10.691}, eprint = {1508.03673}, eprinttype = {arxiv}, - eprintclass = {math.CO}, + eprintclass = {math.CO}, keywords = {published}, - author+an = {1=undergrad; 3=undergrad; 4=undergrad; 5=undergrad}, + abstract = {We consider a generalization of Eulerian numbers which count the number of placements of $cn$ rooks on an $n\times n$ chessboard where there are exactly $c$ rooks in each row and each column, and exactly $k$ rooks below the main diagonal. + The standard Eulerian numbers correspond to the case $c=1$. + We show that for any $c$ the resulting numbers are symmetric and give generating functions of these numbers for small values of $k$. + } } @article{primejuggle, @@ -283,12 +338,18 @@ number = {5}, volume = {32}, pages = {1675--1688}, + url = {https://link.springer.com/article/10.1007/s00373-016-1711-1}, doi = {10.1007/s00373-016-1711-1}, eprint = {1508.05296}, eprinttype = {arxiv}, - eprintclass = {math.CO}, + eprintclass = {math.CO}, keywords = {published}, - author+an = {1=undergrad; 3=undergrad; 4=undergrad; 5=undergrad}, + abstract = {Juggling patterns can be described by a closed walk in a (directed) state graph, where each vertex (or state) is a landing pattern for the balls and directed edges connect states that can occur consecutively. + The number of such patterns of length $n$ is well known, but a long-standing problem is to count the number of prime juggling patterns (those juggling patterns corresponding to cycles in the state graph). + For the case of $b=2$ balls we give an expression for the number of prime juggling patterns of length $n$ by establishing a connection with partitions of $n$ into distinct parts. + From this we show the number of two-ball prime juggling patterns of length $n$ is $(\gamma-o(1))2^n$ where $\gamma=1.32963879259\ldots$. + For larger $b$ we show there are at least $b^{n-1}$ prime cycles of length $n$. + } } @article{loosepath, @@ -301,10 +362,11 @@ number = {2}, volume = {339}, pages = {499--505}, + url = {http://www.sciencedirect.com/science/article/pii/S0012365X15003477}, doi = {10.1016/j.disc.2015.09.026}, eprint = {1411.4058}, - eprinttype = {arxiv}, - eprintclass = {math.CO}, + eprinttype = {arxiv}, + eprintclass = {math.CO}, keywords = {published}, abstract = {For a $k$-uniform hypergraph $G$ with vertex set $\{1,\dots,n\}$, the ordered Ramsey number $\operatorname{OR}_t(G)$ is the least integer $N$ such that every $t$-coloring of the edges of the complete $k$-uniform graph on vertex set $\{1,\dots,N\}$ contains a monochromatic copy of $G$ whose vertices follow the prescribed order. Due to this added order restriction, the ordered Ramsey numbers can be much larger than the usual graph Ramsey numbers. @@ -315,7 +377,7 @@ @article{hanabi, author = {De Silva, Jessica and DeOrsey, Philip and Kenter, Franklin and Retter, Troy and Tobin, Josh}, - title = {How to make the perfect fireworks display: Two strategies for \emph{Hanabi}}, + title = {How to make the perfect fireworks display: Two strategies for <em>Hanabi</em>}, journal = {Mathematics Magazine}, publisher = {Informa UK Limited}, year = {2015}, @@ -323,6 +385,19 @@ number = {5}, volume = {88}, pages = {323--336}, + url = {http://www.jstor.org/stable/10.4169/math.mag.88.5.323}, doi = {10.4169/math.mag.88.5.323}, + % eprint = {https://sites.google.com/site/rmgpgrwc/research-papers/Hanabi_final.pdf}, + % eprinttype = {Preprint}, + extra = {<em>Hanabi</em> simulation code}, + extraurl = {https://github.com/rjtobin/HanSim}, keywords = {published}, + abstract = {The game of Hanabi is a multiplayer cooperative card game that has many similarities to a mathematical ``hat guessing game.'' + In Hanabi, a player does not see the cards in her own hand and must rely on the actions of the other players to determine information about her cards. + This article presents two strategies for Hanabi. + These strategies use different encoding schemes, based on ideas from network coding, to efficiently relay information. + The first strategy allows players to effectively recommend moves for other players, and the second strategy allows players to determine the contents of their hands. + Results from computer simulations demonstrate that both strategies perform well. + In particular, the second strategy achieves a perfect score more than 75 percent of the time. + } } |