Taiki Aiba
Combinatorics & discrete mathematics. Notes and preprints.
Recent notes
4-cycle-free induced subgraphs of grid graphs
Preprint · April 2026 · arXiv:2604.08397
The avoidance of induced forests, or induced acyclic subgraphs, in d-dimensional grid graphs is a question that has received attention in several recent papers. In this note I consider the related question of induced subgraphs that avoid 4-cycles (in the usual sense of induced C4), and give upper and lower bounds on the maximum density of such subgraphs in [n]d. The proofs use a combination of entropy-compression arguments and an explicit lattice construction.
Note on counting induced trees in [n]3
Unpublished · March 2026
A short write-up expanding on a construction that appeared briefly in an earlier draft. The explicit lower bound for induced trees in the three-dimensional grid graph follows from a recursive argument; the same recursion yields a matching upper bound up to a constant factor. I include the details here because they did not fit into the preprint.
On a question of Aharoni and Holzman
Work in progress · 2026
Joint notes with a colleague on a question about rainbow matchings in r-partite r-uniform hypergraphs. We have a partial answer for r = 3 via a direct counting argument; the general case remains open. I expect to post a preprint later this year.
Contact
aiba[at]post[dot]example[dot]ac[dot]jp