Sam Mattheus
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Sam Mattheus has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Francesco Pavese
Politecnico di Bari
4 shared publications - Jacques Verstraëte
Department of Mathematics University of California San Diego 9500 Gilman Drive 92093-0112 La Jolla CA USA
3 shared publications Dhruv Mubayi
Department of Mathematics, Statistics and Computer Science University of Illinois Chicago Chicago Illinois USA
2 shared publicationsJacques Verstraëte
Department of Mathematics University of California San Diego, La Jolla California USA
2 shared publicationsJan De Beule
2 shared publicationsKlaus Metsch
2 shared publications
Latest Publications
- 23 February 2026
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 737, 227-262
An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings II
- 23 February 2026
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 737, 227-262
An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings II
- Open Access
Improved bounds for the minimum degree of minimal multicolor Ramsey graphs
We provide two novel constructions of $r$ edge-disjoint $K_{k+1}$-free graphs on the same vertex set, each of which has the property that every small induced subgraph contains a complete graph on $k$ vertices. The main novelty of our argument is the combination of an algebraic and a probabilistic coloring scheme, which utilizes the beneficial algebraic and combinatorial properties of the Hermitian unital. These constructions improve on a number of upper bounds on the smallest possible minimum degree of minimal $r$-color Ramsey graphs for the clique $K_{k+1}$ when $r\geq c\frac{k}{\log^2 k}$ and $k$ is large enough.Open AccessImproved bounds for the minimum degree of minimal multicolor Ramsey graphs
We provide two novel constructions of $r$ edge-disjoint $K_{k+1}$-free graphs on the same vertex set, each of which has the property that every small induced subgraph contains a complete graph on $k$ vertices. The main novelty of our argument is the combination of an algebraic and a probabilistic coloring scheme, which utilizes the beneficial algebraic and combinatorial properties of the Hermitian unital. These constructions improve on a number of upper bounds on the smallest possible minimum degree of minimal $r$-color Ramsey graphs for the clique $K_{k+1}$ when $r\geq c\frac{k}{\log^2 k}$ and $k$ is large enough. - Open Access
- 28 January 2025
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (1)
Off‐Diagonal Ramsey Numbers for Slowly Growing Hypergraphs
For a k‐uniform hypergraph and a positive integer , the Ramsey number denotes the minimum such that every ‐vertex ‐free ‐uniform hypergraph contains an independent set of vertices. A hypergraph is slowly growing if there is an ordering of its edges such that for each . We prove that if is fixed and is any non‐k‐partite slowly growing ‐uniform hypergraph, then for , In particular, we deduce that the off‐diagonal Ramsey number is of order , where is the triple system . This is the only 3‐uniform Berge triangle for which the polynomial power of its off‐diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs and hypergraph containers.
- 28 January 2025
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (1)
Open AccessOff‐Diagonal Ramsey Numbers for Slowly Growing Hypergraphs
For a k‐uniform hypergraph and a positive integer , the Ramsey number denotes the minimum such that every ‐vertex ‐free ‐uniform hypergraph contains an independent set of vertices. A hypergraph is slowly growing if there is an ordering of its edges such that for each . We prove that if is fixed and is any non‐k‐partite slowly growing ‐uniform hypergraph, then for , In particular, we deduce that the off‐diagonal Ramsey number is of order , where is the triple system . This is the only 3‐uniform Berge triangle for which the polynomial power of its off‐diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs and hypergraph containers.
- 6 November 2024
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 210
Upper bounds for the number of substructures in finite geometries from the container method
- 6 November 2024
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 210
Upper bounds for the number of substructures in finite geometries from the container method
- Open Access
Off-diagonal Ramsey numbers for slowly growing hypergraphs
For a $k$-uniform hypergraph $F$ and a positive integer $n$, the Ramsey number $r(F,n)$ denotes the minimum $N$ such that every $N$-vertex $F$-free $k$-uniform hypergraph contains an independent set of $n$ vertices. A hypergraph is $\textit{slowly growing}$ if there is an ordering $e_1,e_2,\dots,e_t$ of its edges such that $|e_i \setminus \bigcup_{j = 1}^{i - 1}e_j| \leq 1$ for each $i \in \{2, \ldots, t\}$. We prove that if $k \geq 3$ is fixed and $F$ is any non $k$-partite slowly growing $k$-uniform hypergraph, then for $n\ge2$, \[ r(F,n) = Ω\Bigl(\frac{n^k}{(\log n)^{2k - 2}}\Bigr).\] In particular, we deduce that the off-diagonal Ramsey number $r(F_5,n)$ is of order $n^{3}/\mbox{polylog}(n)$, where $F_5$ is the triple system $\{123, 124, 345\}$. This is the only 3-uniform Berge triangle for which the polynomial power of its off-diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs, martingales, and hypergraph containers.Open AccessOff-diagonal Ramsey numbers for slowly growing hypergraphs
For a $k$-uniform hypergraph $F$ and a positive integer $n$, the Ramsey number $r(F,n)$ denotes the minimum $N$ such that every $N$-vertex $F$-free $k$-uniform hypergraph contains an independent set of $n$ vertices. A hypergraph is $\textit{slowly growing}$ if there is an ordering $e_1,e_2,\dots,e_t$ of its edges such that $|e_i \setminus \bigcup_{j = 1}^{i - 1}e_j| \leq 1$ for each $i \in \{2, \ldots, t\}$. We prove that if $k \geq 3$ is fixed and $F$ is any non $k$-partite slowly growing $k$-uniform hypergraph, then for $n\ge2$, \[ r(F,n) = Ω\Bigl(\frac{n^k}{(\log n)^{2k - 2}}\Bigr).\] In particular, we deduce that the off-diagonal Ramsey number $r(F_5,n)$ is of order $n^{3}/\mbox{polylog}(n)$, where $F_5$ is the triple system $\{123, 124, 345\}$. This is the only 3-uniform Berge triangle for which the polynomial power of its off-diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs, martingales, and hypergraph containers. - 2 April 2024
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 56 (6) , 2014-2023
Ramsey numbers and the Zarankiewicz problem
Building on recent work of Mattheus and Verstraëte, we establish a general connection between Ramsey numbers of the form for a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an by ‐matrix that does not have any matrix from a fixed finite family derived from as a submatrix. As an application, we give new lower bounds for the Ramsey numbers and , namely, and . We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of for any fixed integer .
- 2 April 2024
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 56 (6) , 2014-2023
Ramsey numbers and the Zarankiewicz problem
Building on recent work of Mattheus and Verstraëte, we establish a general connection between Ramsey numbers of the form for a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an by ‐matrix that does not have any matrix from a fixed finite family derived from as a submatrix. As an application, we give new lower bounds for the Ramsey numbers and , namely, and . We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of for any fixed integer .
- Open AccessThe asymptotics of $r(4,t)$For integers $s,t \geq 2$, the Ramsey numbers $r(s,t)$ denote the minimum $N$ such that every $N$-vertex graph contains either a clique of order $s$ or an independent set of order $t$. In this paper we prove \[ r(4,t) = Ω\Bigl(\frac{t^3}{\log^4 \! t}\Bigr) \quad \quad \mbox{ as }t \rightarrow \infty\] which determines $r(4,t)$ up to a factor of order $\log^2 \! t$, and solves a conjecture of Erdős.Open AccessThe asymptotics of $r(4,t)$For integers $s,t \geq 2$, the Ramsey numbers $r(s,t)$ denote the minimum $N$ such that every $N$-vertex graph contains either a clique of order $s$ or an independent set of order $t$. In this paper we prove \[ r(4,t) = Ω\Bigl(\frac{t^3}{\log^4 \! t}\Bigr) \quad \quad \mbox{ as }t \rightarrow \infty\] which determines $r(4,t)$ up to a factor of order $\log^2 \! t$, and solves a conjecture of Erdős.
- 11 July 2022
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 192
An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings
- 11 July 2022
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 192
An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings
- Open Access
- 24 May 2022
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 90 (12) , 2943-2966
Moderate-density parity-check codes from projective bundles
New constructions for moderate-density parity-check (MDPC) codes using finite geometry are proposed. We design a parity-check matrix for the main family of binary codes as the concatenation of two matrices: the incidence matrix between points and lines of the Desarguesian projective plane and the incidence matrix between points and ovals of a projective bundle. A projective bundle is a special collection of ovals which pairwise meet in a unique point. We determine the minimum distance and the dimension of these codes, and we show that they have a natural quasi-cyclic structure. We consider alternative constructions based on an incidence matrix of a Desarguesian projective plane and compare their error-correction performance with regards to a modification of Gallager’s bit-flipping decoding algorithm. In this setting, our codes have the best possible error-correction performance after one round of bit-flipping decoding given the parameters of the code’s parity-check matrix.
- 24 May 2022
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 90 (12) , 2943-2966
Open AccessModerate-density parity-check codes from projective bundles
New constructions for moderate-density parity-check (MDPC) codes using finite geometry are proposed. We design a parity-check matrix for the main family of binary codes as the concatenation of two matrices: the incidence matrix between points and lines of the Desarguesian projective plane and the incidence matrix between points and ovals of a projective bundle. A projective bundle is a special collection of ovals which pairwise meet in a unique point. We determine the minimum distance and the dimension of these codes, and we show that they have a natural quasi-cyclic structure. We consider alternative constructions based on an incidence matrix of a Desarguesian projective plane and compare their error-correction performance with regards to a modification of Gallager’s bit-flipping decoding algorithm. In this setting, our codes have the best possible error-correction performance after one round of bit-flipping decoding given the parameters of the code’s parity-check matrix.
- 4 March 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (7)
A clique-free pseudorandom subgraph of the pseudo polarity graph
- 4 March 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (7)
A clique-free pseudorandom subgraph of the pseudo polarity graph