# Research

Interests: Incidence Geometry, Extremal Combinatorics, Spectral Graph Theory, and Polynomial Methods.

All my preprints are available on arXiv. Also see my google scholar page and my CV.

Publications/Preprints

[1] On semi-finite hexagons of order (2, t) containing a subhexagon, with Bart De Bruyn. Annals of Combinatorics. Volume 20, Issue 3 (2016), 433–452. arXiv, journal.

Inspired by a famous open problem posed by Jacques Tits on existence of semi-finite generalized polygons, for which no progress has been made so far in the case of generalized hexagons, we solve a specific case of an easier version of the problem where non-existence is proved after assuming that the generalized hexagon contains a particular subhexagon. We show that (a) no generalized hexagon contains $H(2)$ as a full proper subgeometry, (b) every near hexagon containing $H(2)^D$ is a finite generalized hexagon, and hence isomorphic to $H(2)^D$ or the triality hexagon $T(8, 2)^D$ via the classification result of Cohen and Tits.
The following computer code constructs Table 1 and 2, and verifies Lemma 3.1: GSplit2.g.

[2] A new near octagon and the Suzuki tower, with Bart De Bruyn. Electronic Journal of Combinatorics. Volume 23, Issue 2 (2016), #P2.35. arXiv, journal.

Bart and I discovered a new near octagon corresponding to the finite simple group $G_2(4)$ in July 2014. Here we give its construction, prove several of its properties, and find a “Suzuki tower of near polygons” corresponding to the Suzuki tower of finite simple groups. We also give geometric constructions of some well known strongly regular graphs using this new near octagon and its subgeometries. Moreover, we construct another new near octagon as a subgeometry, related to the group $L_3(4)$.

[3] On Zeros of a Polynomial in a Finite Grid, with Pete L. Clark, Aditya Potukuchi and John R. Schmitt. Combinatorics, Probability and Computing. Volume 27, Issue 3 (2018), 310–333. arXiv, journal.

We prove a generalization of a result of Alon and Füredi, and show how this elementary result on zeros of polynomials is connected to various other results in Coding Theory, Finite Geometry and Theoretical Computer Science. This in combination with the earlier work of Clark, Forrow and Schmitt suggest that much like Combinatorial Nullstellensatz, the Alon-Füredi Theorem is a fundamental result on polynomials with connections to various important topics in mathematics. Here is a video of a talk I gave on this paper to a general scientific audience.

[4] Characterizations of the Suzuki tower near polygons, with Bart De Bruyn. Designs, Codes and Cryptography. Volume 84, Issue 1 (2017), 115–133. arXiv, journal.

We prove uniqueness results for the near polygons lying in the Suzuki tower, that we described in [2]. In particular, we prove a characterization of the Hall-Janko near octagon as the unique near octagon of order $(2, 4)$ containing the dual split Cayley hexagon $\mathrm{H}(2)^D$ as a subgeometry. The following computer codes construct Table 1, 2, 3 and 4, and verify Lemmas 4.12, 5.1, 5.2, 5.3, 5.4: Suz1.g, Suz2.g, HallJankoHyp.g. Also see this for an independent verification by Bart.

[5] Some non-existence results for distance-$j$ ovoids in small generalized polygons, with Ferdinand Ihringer. arXiv, journal (the journal version is much shorter)

We show that the dual split Cayley generalized hexagon $\mathrm{H}(4)^D$ does not have any distance-$2$ ovoids (which are equivalent to exact hitting sets in the corresponding $5$-regular $5$-uniform hypergraph on $1365$ vertices), and that the Ree-Tits octagon $\mathrm{GO}(2, 4)$ does not have any distance-$3$ ovoids, thus resolving the last remaining case for existence of distance-$3$ ovoids in known finite generalized octagons. The computational techniques we use, which combine Knuth’s Dancing Links, Linton’s SmallestImageSet, Integer Linear Programming, along with a nice trick involving subgeometries, might be useful in small cases of other finite geometrical problems that have a similar flavour. Our complete computer code is available here.

[6] On generalized hexagons of order $(3, t)$ and $(4, t)$ containing a subhexagon, with Bart De Bruyn. European Journal of Combinatorics.Volume 62 (2017), 115–123. arXiv, journal, blog.

We extend the work done in [1] by proving that there is no semi-finite hexagon containing any of the known generalized hexagons of order $(3, 3)$ and $(4, 4)$ as full subgeometry. Moreover, we show that the split Cayley hexagon $\mathrm{H}(4)$ is not contained in any generalized hexagon as a full subgeometry. The code in main.g constructs computer models of small generalized hexagons that we use in our computations and the code in main.sage performs all the computations mentioned in Section 4.

[7] The $\mathrm{L}_3(4)$ near octagon, with Bart De Bruyn. Journal of Algebraic Combinatorics. Volume 48, Issue 1 (2018), 157–178. arxiv, journal.

We give an alternate direct construction of one of the near octagons discovered in [2] using the projective special linear group $\mathrm{PSL}_3(4)$. This construction is used to derive geometric and group theoretic properties of this near octagon, and we propose a new family of near octagons to which both this $\mathrm{L}_3(4)$ near octagon and the $\mathrm{G}_2(4)$ near octagon discovered in [2] belong. So far, these are the only two nontrivial members of this family that we know (we define and classify the trivial ones in the paper).

[8] Minimal multiple blocking sets, with Sam Mattheus and Jeroen Schillewaert. Electronic Journal of Combinatorics. Volume 25, Issue 4 (2018),#P4.66. arxiv, journal.

Using the expander mixing lemma, we prove the first non-trivial upper bound on the size of a minimal t-fold blocking set in a finite projective plane. This generalises a classical result of Bruen and Thas. The techniques used also give new proofs of some old and new results in finite geometry. We talk about the sharpness of our result, some constructions, and generalizations.

[9] On regular induced subgraphs of generalized polygons. With John Bamberg and Gordon Royle. Journal of Combinatorial Theory, Series A. Volume 158 (2018), 254–275. arXiv, journal.

The cage problem asks for the smallest graph with a given degree $k$ and girth $g$. The number of vertices in the smallest graph is denoted by $c(k, g)$, and graphs meeting this bound are called cages. The only known non-trivial infinite families of cages are the generalized polygons, which tell us that $c(k, g) = 2((k-1)^{g/2 - 1} + (k-1)^{g/2 - 2} + \cdots + 1)$ for $g \in \{6, 8, 12\}$, whenever $k - 1$ is a prime power. We improve the known upper bounds on $c(k, 8)$ and $c(k, 12)$ for infinitely many values of $k$ by constructing new small regular induced subgraphs of known generalized quadrangles and hexagons. We also give a lower bound on the smallest number of vertices in a regular induced subgraph of a generalized polygon, using the expander mixing lemma, which gives a limit to our methods in improving the upper bounds on cage numbers.

[10] A generalization of the theorems of Chevalley-Warning and Ax-Katz via polynomial substitutions. With Ioulia N. Baoulina and Pete L. Clark. Proceedings of the AMS 147 (2019), 4107–4122. arXiv, journal.

We prove a new generalization of the classical Chevalley-Warning theorem, Ax-Katz theorem and several related results.

[11] Non-intersecting Ryser hypergraphs, with Valentina Pepe. SIAM J. Discrete Math. 34 (2020), 230–240.  arXiv, journal.

Ryser’s conjecture is a longstanding open problem in combinatorics, which states that every $r$-partite, $r$-uniform hypergraph has a vertex cover of size at most $(r - 1)$ times the matching number of the hypergraph. For $r = 2$, this is just Konig’s theorem, and besides that value of $r$ the conjecture is only known to be true for $r = 3$. In recent years, extremal hypergraphs with respect to this conjecture, known as Ryser hypergraphs, have been studied extensively. We contribute to their study by giving new infinite families of non-intersecting Ryser hypergraphs, for uniformity at least $4$, that cannot be built by taking disjoint copies of intersecting Ryser hypergraphs (and possibly adding some new edges), as was known to be true for $3$-uniform hypergraphs. In this sense, it is the first really non-intersecting infinite family of Ryser hypergraphs.

[12] A construction for clique-free pseudorandom graphs, with Ferdinand Ihringer and Valentina Pepe. Combinatorica 40 (2020), 307-314. arXiv, journal.

We construct a new family of optimally pseudorandom graphs that have no subgraphs isomorphic to a clique of fixed size $k$, and have higher edge density than the best known construction of Alon and Krivelevich.

[13] Ryser’s conjecture for $t$-intersecting hypergraphs, with Shagnik Das, Patrick Morris and Tibor Szabó. arXiv, journal, blog. To appear in Journal of Combinatorial Theory, Series A.

We improve known results for the problem of bounding the minimum cover number of an $r$-partite $r$-uniform $t$-intersecting hypergraph, and for $t > r/3$ we obtain sharp bounds. We also introduce various variants of Ryser’s conjecture and prove some initial results for them.

[14] The minimum degree of minimal Ramsey graphs for cliques, with John Bamberg and Thomas Lesgourgues. arXiv, blog.

Using a group theoretical model of generalized quadrangles, due to Kantor from 1980’s, we improve the general upper bound on a Ramsey parameter introduced by Burr, Erdős and Lovász in 1976.

[15] Subspace coverings with multiplicities, with Simona Boyadzhiyska, Shagnik Das and Tamás Mészarós. arXiv, blog.

Talks

1. On semi-finite hexagons of order (2,t) containing a subhexagon of order 2, Fourth Irsee Conference (2014), slides.
2. The Alon-Füredi bound, British Combinatorial Conference 2015, slides.
3. Computing hyperplanes of near polygons, COCOA 2015, slides.
4. On zeros of a polynomial in a finite grid: the Alon-Füredi bound, Combinatorics 2016 and at Discrete Mathematics Days 2016, slides.
5. Zeros of polynomials over a finite grid, polynomial method workshop in HUJI organised by Jordan Ellenberg and Gil Kalai, 2016.
6. Zeros of polynomials over a finite grid, Caltech combinatorics seminar and UCLA combinatorics seminar, 2017.
7. Expander mixing lemma in finite geometry, UWA combinatorics seminar, 2017.
8. The cage problem and finite geometry, Fq13, 2017.
9. Minimal multiple blocking sets, Irsee, 2017, slides.
10. Extremal problems in finite geometry, BMS-BGSMath Junior Meeting 2017, Institut d’Estudis Catalans, Barcelona, slides.
11. Improved bounds on cage numbers, Combinatorics 2018, Facets of Complexity (colloquium talk), and the Berlin-Poznań-Hamburg Seminar.
12. Extremal and near extremal constructions for Ryser’s conjecture, 1st Southwestern German Workshop on Graph Theory, 2018.
13. Extremal problems in finite geometry, Humboldt Network Meeting, Leipzig, 2019.
14. Clique-free pseudorandom graphs, Finite Geometry and Extremal Combinatorics conference, University of Delaware, 2019.
15. Clique-free pseudorandom graphs,  42nd ACCMCC, 2019.
16. The Chevalley-Warning theorems, UWA combinatorics seminar, 2020.
17. Clique-free pseudorandom graphs, TU Delft optimization seminar, 2020.
18. What is Ramsey Theory?, TU Delft Lunch Colloquium, Nov 2020.
19. Lower bounds for diagonal Ramsey numbers, FU Berlin Combinatorics seminar, Nov 2020.
20. Subspace coverings with multiplicities, UvA general mathematics colloquium, Feb 2021.
21. The minimum degree of minimal Ramsey graphs for cliques, Georgia tech combinatorics seminar, Feb 2021.

Collaborators

John Bamberg (2), Ioulia N. Baoulina (1), Simona Boyadzhiyska (1), Pete L. Clark (2), Shagnik Das (2), Bart De Bruyn (5), Ferdinand Ihringer (2), Thomas Lesgourgues (1), Sam Mattheus (1), Tamás Mészarós (1), Patrick Morris (1), Valentina Pepe (2), Aditya Potukuchi (1), Gordon Royle (1), Jeroen Schillewaert (1), John R. Schmitt (1), Tibor Szabó (1).