# Algebraic Graph Theory - Daniel Horsley

Monday, November 21, 2022 — 6:00 PM EST

Title: Exact Zarankiewicz numbers through linear hypergraphs

 Speaker: Daniel Horsley Affiliation: Monash University Location: Contact Sabrina Lato for Zoom link

Abstract: The \emph{Zarankiewicz number} $Z_{2,2}(m,n)$ is usually defined as the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that has no $K_{2,2}$ subgraph. An equivalent definition is that $Z_{2,2}(m,n)$ is the greatest total degree of a linear hypergraph with $m$ vertices and $n$ edges. A hypergraph is \emph{linear} if each pair of vertices appear together in at most one edge. The equivalence of the two definitions can be seen by considering the bipartite incidence graph of the linear hypergraph.

A simple argument determines the exact value of $Z_{2,2}(m,n)$ whenever $n \geq \binom{m}{2}$. Guy was able to extend this determination to all $n \geq \binom{m}{2}/3+\frac{m+1}{3}$. This talk discusses how we can find, for large $m$, the exact value of $Z_{2,2}(m,n)$ in almost all of the remaining cases where $n=\Theta(m^2)$. Our results can be generalised to the Zarankiewicz numbers $Z_{2,\lambda+1}(m,n)$ by considering hypergraphs in which each pair of vertices appear together in at most $\lambda$ edges.

Event tags

### April 2023

S M T W T F S
26
27
28
29
30
31
1
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
1. 2023 (37)
1. April (2)
2. March (17)
3. February (10)
4. January (8)
2. 2022 (150)
1. December (8)
2. November (18)
3. October (15)
4. September (11)
5. August (2)
6. July (17)
7. June (17)
8. May (10)
9. April (12)
10. March (18)
11. February (10)
12. January (13)
3. 2021 (103)
4. 2020 (119)
5. 2019 (167)
6. 2018 (136)
7. 2017 (103)
8. 2016 (137)
9. 2015 (136)
10. 2014 (88)
11. 2013 (48)
12. 2012 (39)
13. 2011 (36)
14. 2010 (40)
15. 2009 (40)
16. 2008 (39)
17. 2007 (15)