Invited Speakers:
Edwin van Dam, Tilburg University
Title: Pseudo-geometric strongly regular graphs with a regular point
Abstract: We study pseudo-geometric strongly regular graphs whose second subconstituent with respect to a vertex is a cover of a strongly regular graph or a complete graph. By studying the structure of such graphs, we characterize all graphs containing such a vertex, and use our characterization to find many new strongly regular graphs. Thereby, we answer a question posed by Gardiner, Godsil, Hensel, and Royle. We give an explicit construction for q new, pairwise non-isomorphic graphs with the same parameters as the collinearity graph of generalized quadrangles of order (q,q) and a new non-geometric graph with the same parameters as the collinearity graph of the Hermitian generalized quadrangle of order (q^2,q), for prime powers q.
Joint work with Kristal Guo.
Robert Jajcay, Comenius University Bratislava
Title: Group based constructions of $k$-regular graphs of large girth and small degree
Abstract: The {\em Cage Problem} is the problem of finding a $k$-regular graph of girth $g$
and smallest possible order, for given $k,g \geq 3$. Even though the smallest $k$-regular graphs
of girth $g$ do not have to admit many symmetries, the majority of them do. Thus, searching for
smallest $k$-regular graphs of girth $g$ among vertex-transitive graphs or graphs with a large
automorphism group and only a small number of orbits proved repeatedly productive, and beside
constructions based on geometry and generalized polygons, it is the direction of research considered by almost all researchers in the area.
In our talk we will discuss three constructions which involve the selection of an appropriate group, a set of generators and/or subgroups.
The three main constructions discussed will be the {\em Cayley graph construction}, the {\em voltage graph construction} and the {\em bi-coset graph construction}.
We will present basic descriptions of all three of these constructions together with some examples,
and then we will discuss the relative advantages and disadvantages of each of these constructions with regard to the Cage Problem.
Daniel Kráľ (Masaryk University, Brno, Czech Republic)
Title: Spectral method in extremal combinatorics
Abstract: We will present two recent applications of spectral arguments in extremal
combinatorics. The first concerns a quantitative version of Ramsey's Theorem.
A graph G is common if the random 2-edge-coloring of a complete graph
asymptotically minimizes the number of monochromatic copies of G
among all 2-edge-colorings. The notion of common graphs can be traced back
to the work of Erdős from the 1960s. In particular, Erdős conjectured that
every complete graph is common, which was disproved by Thomason in the 1980s.
A classification of common graphs remains a challenging open problem.
Sidorenko's Conjecture, one of the most significant open problems in extremal
graph theory, implies that every 2-chromatic graph is common. While examples of
3-chromatic common graphs were known for a long time, the existence of
a 4-chromatic common graph was open until 2012. Using spectral arguments
in the setting of graph limits, we establish the existence of connected common
graphs with an arbitrarily large chromatic number.
The second application concerns a classical problem on maximizing the density of
a fixed subgraph. Specifically, we study the asymptotic behavior of the maximum
number of cycles of a given length in a tournament: let c(k) be the limit of
the ratio of the maximum number of cycles of length k in an n-vertex tournament and
the expected number of cycles of length k in the random n-vertex tournament,
when n tends to infinity. We will show that c(k)=1 if and only if k is not divisible
by four, which settles a conjecture of Bartley and Day. Moreover, if k is even
but not divisible by four, then every extremal tournament is quasirandom.
The talk will include results obtained with different groups of collaborators,
including Andrzej Grzesik, László Miklós Lovász, Jonathan A. Noel, Sergey Norin,
Jan Volec and Fan Wei.
Tamás Szőnyi, Eötvös Loránd University and University of Primorska
Title: On large minimal blocking sets in projective planes of square order
Abstract: A {\em blocking set} in a projective plane is a set of points which intersects every line. The smallest blocking sets are lines. A blocking set is {\em minimal} when no proper subset of it is a blocking set. We shall discuss two basic problems about blocking sets. The first one is about the size of the smallest blocking set not containing a line, the second one is about the size of the largest minimal blocking set.
The talk will focus on the second problem.
Minimal blocking sets in planes of order $q^2$ have size at most $q^3+1$.
This result is due to Bruen and Thas and the bound is sharp, sets attaining this bound are called unitals. Blokhuis and Metsch proved that in ${\rm PG}(2,q^2)$ there are no minimal blocking sets with cardinality $q^3$, when $q\geq 7$.
In this talk, we show that the second largest minimal blocking sets have size at most $q^3+1-(p-3)/2$, if $q=p$, $p \geq 67$, or $q = p^h$, $p > 7$, $h > 1$.
Our proof also works for sets having at least one tangent at each of its points (that is, for tangency sets).
A stronger result was obtained by Ball for so-called partial unitals.
The results are joint works with Zsuzsa Weiner.
