MTA-ELTE Geometric and Algebraic
Combinatorics Research Group

Finite Geometry Seminar

•  Friday, 14.15-15.45  •  ELTE Southern building, room 3.607  •  Pázmány P. sétány 1/C  •

Program of former semesters

From 2002 Spring

Program of 2018 Fall


Térbeli kvádrikasorok oszályozása + pizza

Dec 14, Porupsánszki István

A jól ismert síkbeli körsorok és kúpszeletsorok egy természetes általánosítása a \(PG(3,q)\)-beli kvádrikasorok. Egy kvádrikasor bázisa egy negyedrendű görbe, amelyet akkor nevezünk reducibilisnek, ha \(GF(q)\) valamely kibővítésében legalább két komponensre bomlik. Főleg azokról a nemszinguláris kvádrikasorokról lesz szó, amelyek bázisa reducibilis. A cél az, hogy megadjunk egy lehetséges osztályozását a kvádrikasoroknak. A kvádrikasorok struktúrájának megértése különböző geometriai problémára adhat megoldást, például hogy hogyan lehet lefedni kvádrikákkal a tér pontjait.

Spreading (linear) triple systems and embedding collinear triples into finite projective planes

Dec 7, Zoltán Lóránt Nagy

A well known and widely open question is to describe good criteria for embedding certain set of lines into a finite projective geometry. Here we propose the following variant of the above question: a set \(P\) of points is given as an underlying set, and a set \(T\) of triples which are prescribed to be collinear. How does the size of \(T\), or its other combinatorial properties, decide whether \(T\) can be realizable by a projective plane of fixed order? The investigation leads us to several interesting problems concerning linear triple systems, namely two different kinds of 'spreading property' make a key role here. We give lower bounds on the minimal size of  linear spreading triple systems applying graph theoretic techniques and upper bounds (constructions) which show connections to subsquare-free Latin squares.
Joint work with Zoltán L. Blázsik

FYI: Uncertainty in finite planes

Nov 27 (Tuesday), 14:00, Renyi Institute, Main Lecture Hall (Number Theory Seminar), András Biró

We establish a number of uncertainty inequalities for the additive group of a finite affine plane, showing that for \(p\) prime, a nonzero function \(f\colon\mathbb{F}_p^2\to\mathbb{C}\) and its Fourier transform \(\hat{f}\colon\widehat{\mathbb{F}_p^2}\to\mathbb{C}\) cannot have small supports simultaneously. Joint work with V.F. Lev.

\(q\)-subresultants and Dickson matrices

Nov 23, Bence Csajbók

Let \(f\) and \(g\) be two \(q\)-polynomials over \(\mathrm{GF}(q^n)\). Following the ideas of Ore and Li we study \(q\)-analogous of scalar subresultants and show how these results can be applied to determine the rank of the common kernel of \(f\) and \(g\). If we put \(g(x)=x^{q^n}-x\), then we obtain conditions on the rank of \(f\). As an application we show how certain minors of the Dickson matrix \(D(f)\), a \(q\)-circulant matrix associated with \(f\), determine the rank of \(D(f)\) and hence the rank of \(f\). To determine the rank of \(q\)-polynomials from their coefficients has been crucial in recent studies of MRD-codes.
Introduce the notion \(D_m(f)\) to denote the \((n-m)\times (n-m)\) matrix obtained from \(D(f)\) after removing its first \(m\) columns and last \(m\) rows. Then our result is as follows.

Theorem:
\(\dim_q (\ker f)=k\) if and only if \(\det D_0(f)= \det D_1(f)=...= \det D_{k-1}(f)=0\) and \(\det D_k(f)\neq 0\).

No seminar

Nov 16

The old and the new proof of Segre's every oval of PG(2,q), q odd, is a conic Theorem

Nov 9, Bence Csajbók

The aim of this talk is to compare two proofs for the above mentioned result in order to understand better Ball's coordinate free version of the Lemma of tangents and its applications.

Extraordinary event: Dominating sets in finite generalized quadrangles

Oct 29 (Monday) 11 am, D-3-607 (the usual seminar room), Lisa Hernandez Lucas (Belgium)

The abstract can be read here in pdf format.

The extended coset leader weight enumerator of a code associated to the twisted cubic

Oct 26, Aart Blokhuis (Eindhoven)

The abstract can be read here in pdf format. Joint work with Ruud Pellikaan and Tamás Szőnyi.

No seminar

Oct 19

External talk in the Rényi Institute: Polymath16 es más újdonságok a sík kromatikus számáról (in Hungarian)

Oct 12, Dömötör Pálvölgyi, Rényi Institute Lecture Room

Miota az ev elejen de Grey bebizonyitotta, hogy a sik kromatikus szama legalabb 5, nagyon gyorsan jottek a kulonbozo ezzel kapcsolatos eredmenyek, polymath projekt is indult a temaban tobbek kozott de Grey es Tao kozremukodesevel. Eloadasom celja, hogy ezeket bemutassam 3 kulonbozo modszeren keresztul. Az elso sikbeli egysegtav-grafok "brute force" keresese; itt 553 csucs a rekord, de csak szamitogeppel ellenorizheto, hogy ennek a grafnak nincs 4-szinezese. Errol nem fogok sokat mondani...
A masodik egy valoszinusegi modszer, mely minden d tavolsagra becsleseket ad arra hogy ket, egymastol d-re levo pont mekkora esellyel lesz azonos szinu. (Fontos, hogy az amenabilitas miatt itt sem kell feltenni, hogy a szinezes merheto.) Itt egy erdekes eredmeny, hogy ha az 1-en kivul még egyetlen d tavolsagot megtiltunk, akkor a kromatikus szam legalabb 5 barmely \(\sqrt{2} < d < 2\)-re; ez az eredmeny gyengebb, mint az elozo, de nem igenyel szamitogepet, el is mondom a teljes bizonyitast.
A harmadik pedig Frankl Noraval es Hubai Tamassal kozos eredmenyem, mely Gallai egy szinezesi tetelenek felhasznalasaval arra ad egy modszert, hogy egy egysegtav-graf egy adott csucsarol feltehessuk, hogy ket szinnel kell szinezni (azaz a szomszedainal ket szin is tiltva van). Az adott csucs szomszedairol egyelore meg kell kovetelnunk, hogy egy szep racson vannak, igy nem sikerult az 553-at sokkal lejjebb vinnunk, de azt sejtjuk, hogy ettol a felteteltol meg lehet szabadulni; enelkul 24 csucsu grafok is vannak, amik kezzel ellenorizheto bizonyitast adnanak. Mondok ezzel kapcsolatban megoldasra varo kerdeseket.

Small weight code words in the code of points and hyperplanes of PG\((n, q)\)

Oct 05, Lins Denaux (Ghent)

The abstract can be read here in pdf format.

Circular-linear one-factorizations of the complete graph \(K_n\)

Sep 28, György Kiss

The abstract can be read here in pdf format.

Program of 2018 Spring

Sidorenko-egyenlőtlenség determinánsokra

May 18, Péter Csikvári

Egy \(G\) gráf és egy \(x \in (0,1)\) számra tekintsük azon pozitív definit \(A\) mátrixokat, melyek átlójában \(1\)-esek vannak és ha két csúcs össze van kötve akkor  \(A_{u,v}=x\). (A nem összekötött csúcspároknál bármi lehet, csak az \(A\) pozitív definitségét kell fenntartani.) Legyen ezen mátrixok közül a legnagyobb determinánsú mátrix determinánsa \(\tau(G,x)\). Szegedy Balázs sejtette és közösen bizonyítottuk, hogy \(\tau(G,x) \geq \tau(K_2,x)^{e(G)}=(1-x^2)^{e(G)}\), ahol \(e(G)\) a \(G\) éleinek száma. Az előadásomban el fogom mesélni, honnan jön ez a furcsa sejtés, mi köze az eredeti Sidorenko-sejtéshez és hogyan kapcsolódik Brendan McKay egy feszítőfák számára vonatkozó tételéhez.

University Break (Eötvös Day & Pázmány Day)

May 11

Stabilitási eredmény projektív terek felső kromatikus számával kapcsolatban

April 27 May 4, Zoltán Blázsik

Általában egy \(H(V,E)\) hipergráf esetén valódi \(N\)-színezésről beszélünk, ha a \(V\) halmazt úgy partícionáljuk \(N\) osztályra, hogy egyik sem üres. Egy hiperélt szivárványnak nevezünk, ha minden színosztályből legfeljebb \(1\) elemet tartalmaz. A hipergráf felső kromatikus számának nevezzük azt a legnagyobb \(N\) számot, amire a hipergráfnak van olyan valódi \(N\)-színezése, amiben nincsenek szivárvány hiperélek (szivárványmentes). Egy nemnegatív \(t\) szám esetén a \(T \subseteq V\) részhalmazt a hipergráf \(t\)-transzverzálisának nevezzük, ha a \(T\) mindegyik hiperélbe legalább \(t\) elemben belemetsz. A hipergráf egy színezését triviálisnak nevezzük, ha tartalmaz egyszínű \(2\)-transzverzálist.
Az előadásban az \(n\)-dimenziós projektív tér pontjai és \(k\)-dimenziós alterei által meghatározott hipergráf szivárványmentes színezéseit vizsgáljuk. Vegyük észre, hogy a nem egyelemű színosztályok uniója egy 2-transzverzális, vagy máshogy fogalmazva egy kétszeresen \((n-k)\)-lefogó ponthalmaza a projektív térnek. Az előadás célja, hogy egy olyan sziváránymentes színezésről, melyben a nem egyelemű színosztályok uniójának mérete az elméleti minimális méretét (\(2q^{n-k}\)) egy kétszeresen \((n-k)\)-lefogó ponthalmaznak csak egy kicsivel (kb \(q^{n-k}/17\)-tel) haladja meg, megmutassuk, hogy triviális kell legyen (azaz tartalmaznia kell egyszínű kétszeresen \((n-k)\)-lefogó ponthalmazt).
Közös munka Héger Tamással, Kovács Istvánnal és Szőnyi Tamással.

MRD codes with maximum idealizers

April 20, Bence Csajbók

Left and right idealizers are important invariants of linear rank metric codes. In case of \(n\times n\) MRD codes over \(\mathrm{GF}(q)\) the idealizers have been proved to be isomorphic to finite fields of size at most \(q^n\). Up to now, the only known MRD codes with maximum left and right idealizers are the generalized Gabidulin codes. I present some new constructions and classification results. It turned out that the existence of such codes is strongly related to some classical results from finite geometry and finite field theory.
This is a joint work with Olga Polverino, Giuseppe Marino and Yue Zhou.

Planar arcs, a recent paper by Simeon Ball and Michel Lavrauw

April 13, Aart Blokhuis (Eindhoven)

The abstract can be read here in pdf format.

Small weight codewords in the code of points and hyperplanes of \(\mathrm{PG}(n, p)\), \(p\) prime

April 6, Leo Storme (Ghent University)

The abstract can be read here in pdf format.

Easter break

March 30

Special seminar: New definitions for Cameron-Liebler sets & Classification of hyperovals and KM-arcs in small projective planes

March 28 (Wednesday!) 1:30 PM (!), Jozefien D'haeseleer & Peter Vandendriessche

A Cameron-Liebler set is a set of subspaces in a fixed finite projective space, that has many equivalent definitions. Cameron and Liebler started with a Cameron-Liebler line set \(S\) in \(\mathrm{PG}(3, q)\), which is a set of lines, so that every line spread in \(\mathrm{PG}(3, q)\) has the same number of lines in common with \(S\). After a large number of results regarding Cameron-Liebler sets of lines in the projective space \(\mathrm{PG}(3, q)\), Cameron-Liebler sets of \(k\)-spaces in the \((2k+1)\)-dimensional projective space \(\mathrm{PG}(2k+1, q)\) were defined. In addition, this research started the motivation for defining and investigating Cameron-Liebler sets of generators in polar spaces. In this talk I will discuss a new definition for Cameron-Liebler sets in projective and polar spaces, where I will use the theory of association schemes. By using this new definition, we try to give a classification result for Cameron-Liebler \(k\)-sets in \(\mathrm{PG}(n, q)\).

Hyperovals (resp. KM-arcs) are point sets in \(\mathrm{PG}(2,q)\) (resp. in \(\mathrm{AG}(2,q)^D\)) such that every line contains 0 or 2 of these points. Every hyperoval can be seen as a KM-arc, but not vice versa; both only exist when \(q\) is even. Hyperovals always have size \(q+2\), KM-arcs have size \(q+t\) for some \(t\mid q\). A commonly studied problem for any projective substructure is to classify its examples in small projective planes. We give an overview of the known results, with particular focus on the most recent result: a full classification of the KM-arcs in \(\mathrm{PG}(2,64)\).

A Carlitz type result for linearized polynomials

March 23, Giuseppe Marino

The abstract can be read here in pdf format.

Holiday

March 16

No seminar

March 9

Discrete Fuglede Conjecture and Pompeiu problem

March 2, Gábor Somlai

The abstract can be read here in pdf format.

Double blocking sets of size \(3q-1\) in \(\mathrm{PG}(2,q)\)

Feb 23, Tamás Héger

We report on constructions of minimal double blocking sets of size \(3q-1\) in \(\mathrm{PG}(2,q)\) for \(q=13\), \(16\), \(19\), \(25\), \(31\), \(37\) and \(43\). These are particularly interesting when \(q\) is prime, because in that case, no examples of double blocking sets of size less than \(3q\) has been known except for \(q=13\). All of our examples admit two \((q-1)\)-secants and have been found using a computer. Furthermore, we show that a double blocking set in \(\mathrm{PG}(2,q)\) of size \(3q-1\) cannot have three \((q-1)\)-secants. These results partially prove and disprove some conjectures of R. Hill from 1984. Joint work with Bence Csajbók.

Program of 2017 Fall

Az André-Bruck-Bose reprezentációról és a deriválásról - folytatás.

Dec 8, Héger Tamás

Az André-Bruck-Bose reprezentációról és a deriválásról.

Dec 1, Héger Tamás

A counterexample to Stein's Equi-n-square Conjecture.

Nov 24, János Barát

In 1975 Stein conjectured that in every \(n\times n\) array filled with the numbers \(1,\ldots,n\) with every number occuring exactly \(n\) times, there is a partial transversal of size \(n−1\).  In this talk we present the recent paper of Pokrovskiy and Sudakov which shows that this conjecture is false and construct such arrays without partial transverals of size \(n-C\log(n)\).

Corollaries of a finite field contraction in the spirit of Mors and Furedi; and an alternative way to construct the projective planes \(\mathrm{PG}(2,q)\).

Nov 17, Zoltán Lóránt Nagy

We show an asymptotically tight result for the lower bound on  the number of copies of \(K_{2,t}\) graphs in balanced bipartite graphs, in terms of the number of edges, if the excess over the extremal number \(ex_{bi}(n+n, K_{2,t})\) is at least of order \(n\sqrt{n}\). We also point out that the applied construction yields a good bound on certain bipartite Ramsey numbers as well.  Finally, we present a novel construction of the projective plane over a finite field via the solutions of a Vandermonde-type matrix-equality. 

On sets of points with few odd secants.

Nov 10, Bence Csajbók

Let \(S\) be a set of \(q+2\) points in \(\mathrm{PG}(2,q)\), \(q\) odd. An odd secant of \(S\) is a line incident with an odd number of points of \(S\). A conjecture from [1] states that the number of odd secants of \(S\) is at least \(2q-2\). Observe that a conic, together with an external point is a set of \(q+2\) points with \(2q-2\) odd secants. In this talk we prove asymptotically this conjecture up to a constant, that is, we show that there is a constant \(c\) and a \(K\) such that the number of odd secants of \(S\) is at least \(2q-c\) for \(q > K\). This is a joint work with Simeon Ball.

[1] P. Balister, B. Bollobás, Z. Füredi and J. Thompson, Minimal symmetric differences of lines in projective planes, J. Combin. Des., 22 (2014) 435-451.

Break

Nov 3.

Hegyeshalmok - mik ezek és mekkorák? (Improved bounds for acute sets)

Oct 27, Gerencsér Balázs

Erdős először 1950 körül vetette föl a következő problémát: hány pontot lehet lehet \(\mathbb{R}^d\)-ben úgy megválasztani, hogy minden általuk alkotott szög hegyesszög legyen? Évtizedekig a legjobb alsó és felső becslés csak rendkívül lassan közeledett egymáshoz, viszont az elmúlt fél évben felgyorsultak az események. Ebben az előadásban elmeséljük ennek a fordulatos történetét, vázolva a konstrukciókat és bizonyításokat. Harangi Viktorral közös munka.

Lefogó ponthalmazok  diszjunkt Baer-részsíkok uniójára vonatkozóan.

Oct 20, Szőnyi Tamás

Egy \(q^2\) rendű Galois-síkon tekintsük a \(t\) diszjunkt Baer-részsík pontjai és egyenesei alkotta reguláris es uniform illeszkedési struktúrát. Ebben keressük a minimális méretű lefogó ponthalmazokat. Ha \(t\) kicsi, ezek \(t\) darab részegyenes uniói (minden részsíkban annak egy egyenesét vesszük), azaz \(t(q + 1)\) pontból állnak. Ha \(t\) nagy (azaz \(q^2 - q\)  közelében van), akkor viszont egy Baer-részsíkot kell vennünk, azaz a legkisebb méret \(q^2 + q + 1\). Az előadás ezt a problémát járja körül. Az eredmények Aart Blokhuis-szal és Leo Storme-val közösek.

An overview of codes arising from projective spaces.

Oct 13, Ferdinando Zullo (Caserta (IT))

Let us consider the projective space \(\mathrm{PG}(n,q)\) with \(n>1\) (\(q\) possibly not a prime power, if \(n=2\)). We define the incidence matrix \(A=(a_{i,j})\) of \(\mathrm{PG}(n,q)\) as the matrix whose rows are indexed by \(t\)-spaces of \(\mathrm{PG}(n,q)\) and whose columns are indexed by the \(s\)-spaces of \(\mathrm{PG}(n,q)\), and with entries \[ a_{i,j}= \left\{ \begin{array}{llrr} 1 & \text{if \(s\)-space \(j\) is contained in \(t\)-space \(i\),} \\ 0 & \text{otherwise.} \end{array} \right. \] The linear code over \(\mathbb{F}_p\), where \(p\) is a prime, generated by the rows of the matrix \(A\) is denoted by \(\mathcal{C}_{s,t}(n,q)\). The interest in these codes started after the works of E. Prange and L. D. Rudolph, which showed that projective planes could be used to define error-correcting codes. In this talk I will report on the state of the art in such codes, and provide some open problems on following topics:

  • the parameters of \(\mathcal{C}_{s,t}(n,q)\), \(\mathcal{C}_{s,t}(n,q)^\perp\) and \(\mathcal{C}_{s,t}(n,q)\cap\mathcal{C}_{s,t}(n,q)^\perp\);
  • weight distributions and nature of codewords;
  • the case of non-Desarguesian planes.

Program of 2017 Spring

Fourier analysis in the problem of MUBs (mutually unbiased bases) and of the existence of finite projective planes

May 5, 15:15-16:15, Mihály Weiner (BME)

Maximum scattered linear sets of \(\mathrm{PG}(1,q^n)\)

Apr 21, Ferdinando Zullo (Università della Campania "Luigi Vanvitelli", Italy)

In this talk we will investigate maximum scattered linear sets of \(\mathrm{PG}(1,q^n)\). A point set \(L_U\) of \(\mathrm{PG}(1,q^n)=\mathrm{PG}(W,\mathbb{F}_{q^n})\) is said to be an \(\mathbb{F}_q\)-linear set of rank \(k\) if it is defined by the non-zero vectors of a \(k\)-dimensional \(\mathbb{F}_q\)-vector subspace \(U\) of \(W\) \[L_U=\{\langle { \mathbf{u}} \rangle_{\mathbb{F}_{q^n}} \colon { \mathbf{u}}\in U\setminus \{{ \mathbf{0}} \}\}.\] Also, \(L_U\) is said to be maximum scattered \(\mathbb{F}_q\)-linear set if \(k=n\) and \(\displaystyle |L_U|=\frac{q^n-1}{q-1}\). Recently the theory of maximum scattered \(\mathbb{F}_q\)-linear set has increased its importance mainly because of its connection with MRD-codes, which are intensively studied. This is a joint work with Bence Csajbók, Giuseppe Marino and Olga Polverino.

Computer Classification of Hyperovals and KM-arcs

Apr 7, Peter Vandendriessche (University of Ghent)

In this talk I will speak about the computer classification of hyperovals and KM-arcs in small Desarguesian planes, i.e. \(\mathrm{PG}(2,q)\). The focus will be on the techniques used in the largest plane where a full classification is known; this is currently \(\mathrm{PG}(2,64)\) for both.

Geometrical aspects of subspace codes & Applications of projective planes to extremal graph theory

Mar 31, Leo Storme (Ghent) & Sam Mattheus (Brussels)

The seminar will consist of two separate 45 minute talks.
Leo's abstract: Subspace codes are codes in which the codewords consist of subspaces of a vector space \(V(n,q)\) of dimension \(n\) over the finite field of order \(q\). These codes now receive a lot of attention because of their relevance for transmission of information in wireless networks. Since codewords are subspaces of a vector space \(V(n,q)\), they also can be interpreted as being subspaces of the projective space \(\mathrm{PG}(n-1,q)\) of dimension \(n-1\) over the finite field of order \(q\). This implies that geometrical techniques can be used to construct subspace codes and to investigate properties of subspace codes. In this talk, a number of geometrical results on subspace codes will be presented to show that the theory of subspace codes is a new interesting research domain for finite geometers.
Sam's abstract: Projective planes are often studied on their own, but they make a lot of appearances outside finite geometry. The reason is that because of their very symmetrical structure, they are a perfect candidate to consider in graph theoretical problems. Among these, we will focus on problems in extremal graph theory and show how graphs derived from projective planes appear naturally in this context. New results on some invariants of these graphs will be presented. This is joint work with Leo Storme and Francesco Pavese.

Resolving sets for generalized quadrangles

Mar 17, Tamás Héger

A resolving set of a graph \(G=(V;E)\) is a subset \(S=(s_1,s_2,...,s_k)\) of vertices such that for each vertex of \(V\), its distance list \((d(v,s_1),d(v,s_2),...,d(v,s_k))\) with respect to \(S\) is unique. A smallest resolving set is called a metric basis and its size is the metric dimension of \(G\). In the talk we consider the metric dimension of the incidence graph of a generalized quadrangle of order \((q,q)\), and prove it to be at least \(\max\{6q-71,4q-7\}\) for any GQ, and at most \(8q\) for the classical GQs (\(W(q)\) and \(Q(4,q)\)). Joint work with Daniele Bartoli, György Kiss and Marcella Takáts.

Maximum scattered alterek

Mar 10, Bence Csajbók

Legyen \(V=V(r,q^n)\) egy \(\mathrm{GF}(q^n)\)-feletti \(r\)-dimenziós vektortér, \(n,r>1\), és legyen \(U\) a \(V\)-nek egy \(\mathrm{GF}(q)\)-altere. Az \(U\) altér "scattered", ha a \(V\) egydimenziós \(\mathrm{GF}(q^n)\)-altereit legfeljebb egydimenziós \(\mathrm{GF}(q)\)-alterekben metszi. Ha \(rn\) páros, akkor scattered altér rangja maximum \(rn/2\) lehet, az \(rn/2\)-dimenziós scattered altereket "maximum scattered"-nek nevezzük. Előadásomban három módszert mutatok arra, hogyan lehet \(r=2\) esetén eldönteni egy \(n\)-dimenziós altérről, hogy (maximum) scattered-e vagy sem. Könnyű látni, hogy maximum scattered alterek direkt összege is maximum scattered altér, tehát \(V(2,q^n)\)-beli konstrukciókból könnyen lehet magasabb dimenziós példákat gyártani. Az előadás egy Giuseppe Marinoval, Olga Polverinoval és Corrado Zanellaval közös munkán alapul.

Selectively balancing unit vectors

Mar 03, Aart Blokhuis

A set \(U\) of unit vectors is selectively balancing if there are different subsets \(U^+\) and \(U^-\), such that the Euclidean distance between the sum of the vectors in \(U^+\) and in \(U^-\) is less than \(1\). We prove that the minimum number of unit vectors that guarantee a selectively balancing set in \(\mathbb R^n\) is asymptotically \(\frac12n\log n\). Joint work with Hao Chen.

Resolving sets for higher dimensional projective spaces

Feb 24, György Kiss

Let \(R(n,q)\) be a resolving set for the point-hyparplane incidence graph of \(\mathrm{PG}(n,q)\). In this talk estimates on the size of \(R(n,q)\) are presented. We prove that if \(q\) is large enough then \(|R(n,q)|\geq 2nq-2\frac{n^{n-1}}{(n-2)!}\). This generalizes tha planar result of Héger and Takáts stating that the metric dimension of the point-line incidence graph of a projective plane of order \(q\) is \(4q-4\). Translating the result of Fancsali and Sziklai about higgledy-piggledy lines to the language of resolving sets, we get that If \(q=p^r,\) \(p>n\) and \(q\geq 2n-1\) then \(|R(n,q)|\leq (4n-2)q\). We prove that \(|R(3,q)|\leq 8q\) and \(|R(4,q)|\leq 12q\). In the cases \(p \leq n-1 \) and \(q \leq 2n-2\) we prove \(|R(n,q)| \leq {n^2+n-6}q\). Joint work with Daniele Bartoli, Stefano Marcugini and Fernanda Pambianco.

Program of 2016 Fall

Lépések a  Ryser-sejtés megoldása felé

Dec 9, János Barát

A hypergraph is \(r\)-partite if its vertex set \(V\) can be partitioned into \(r\) sets \(V_1,\dots, V_r\), called the sides of the hypergraph, so that every edge contains at most one vertex from each side. Ryser conjectured the following: In an \(r\)-partite hypergraph, \(\tau\le(r-1)\nu\). Very little is known about this conjecture. It simplifies to \(\tau\le r-1\) for intersecting hypergraphs. Until recently, there was only one family of \(r\)-partite hypergraphs known to attain equality here: subhypergraphs of truncated projective planes. The truncated projective plane of uniformity \(r\) is obtained from a projective plane of order \(r-1\) by the removal of a single vertex \(v\) and the lines containing \(v\). The sides \(V_1,\dots, V_r\) are the sets of vertices other than \(v\) on the lines containing \(v\). We construct new families of $r$-partite hypergraphs that attain Ryser's bound, where \(r\) is different from the value in the previous construction.

Around Wenger graphs

Dec 2, Tamás Héger

Az előadásban az extremális gráfelméleti szempontból is érdekes Wenger-gráfokra és azok változataira vonatkozó eredményeket fogunk ismertetni. A fő hangsúly Cioaba, Lazebnik és Li On the Spectrum of Wenger graphs (JCT B, 2014) cikkén lesz, melyben meghatározzák a Wenger-gráfok spektrumát. A cikk egy érdekes mellékterméke az alábbi feladvány: igazoljuk tetszőleges \(q\geq 3\) és \(1\leq m\leq q-1\) egészekre a (vélhetően igaz) \(\sum_{i=0}^m\binom{q}{i}\sum_{d=i}^{m}\sum_{k=0}^{d-i}(-1)^k\binom{q-i}{k}q^{d-i-k} = \frac{q^{m+1}-1}{q-1}\) azonosságot!

Telítő (saturating, avagy sűrű (dense)) halmazok mérete véges síkokban

Nov 25, 14:00-15:30, Zoltán Nagy

Egy ponthalmazt a veges projektiv sikban surunek nevezunk, ha az altaluk meghatarozott egyenesek lefogjak az osszes pontot. Kis suru halmazok is legalabb \((2q)^{1/2}\) meretuek, es ez a trivialis also becsles nagysagrendben eles is a negyzetrendu Galois sikokon.  A kerdes altalaban a teljes ivek meretevel rokon, hiszen minden teljes iv egyben suru halmaz is. Masik iranybol a kapcsolatot nezve Grynkiewicz es Lev az \(F_2\) feletti terekben igazolja, hogy minden kis suru halmaz ebben a terben vagy teljes suvegbol szarmazik, vagy abbol kis perturbacioval megkaphato (a suveg a magasabb dimenzios terekben az iv analog megfeleloje). Teljes ivek mereterol Kim es Vu (2003) cikke bizonyitja, hogy \(Cq^{1/2}\cdot\log(q)^{10}\) meretut biztos tudunk talalni minden sikban, es sejtese szerint \(Cq^{1/2}\cdot \log(q)^{1/2}\) a helyes nagysagrend. Suru halmazokra nezve eloszor belatjuk fel-random modszerrel, hogy \((3\log(q)q)^{1/2}\) meretut minden sikon talalunk, ez megjavitja az eddigi legjobb, szinten valoszinusegi modszeren alapulo korlatot (Bartoli et al 16+). Ezutan standard egyenletekre tamaszkodo, moho jellegu algoritmust is mutatunk, ami szinten ezt a nagysagrendet eri el.

A hagyomanyostol kisse eltero, kutatoszeminarium-jellegu eloadas varhato, vagyis az eloado a tema hatterenek es uj eredmenyei es reszeredmenyi felvillantasa utan elsosorban a nyitott kerdesekre, es javitasi lehetosegekre helyezi a hangsulyt.

\(H\)-részgráf-mentes gráfok maximális független halmazai, szubexponenciális algoritmusok

Nov 18, Gábor Bacsó

The abstract can be viewed clicking here. Joint work with Dániel Marx and Zsolt Tuza.

Véges projektív síkok partíciódimenziójanak kiszámítása

Nov 11, Zoltán Blázsik and Zoltán Nagy

A partíciódimenzió a metrikus dimenzióhoz hasonlatos fogalom, ez a paraméter szintén a gráfok  -- esetünkben a véges síkok illeszkedési gráfjának -- csúcsait megkülönböztető struktrúra méretének minimumát méri. Korábbi szemináriumi előadásukban Marcella es Tamás a metrikus dimenziót pontosan meghatározta: ha a sík rendje, \(q\) elegendően nagy, akkor a metrikus dimenziója a \(q\)-rendű projektív sík illeszkedési gráfjának \(4q-4\) (v.ö. Héger, Takáts: Resolving sets and semi-resolving sets in finite projective planes, EJC, 19(4) #P30). Esetünkben a partíciódimenzió lényegesen kisebb. Belátjuk, hogy nagyságrendje \((2+o(1)) \log(q)\) és \((4+o(1)) \log(q)\) közé esik. A felső becslés  kétfázisú: sajátos önduális részstruktúrák véletlen választásán, majd algoritmikus javításokon alapul. Bemutatjuk a probléma kapcsolatát a következő kérdéssel is: létezik-e diszjunkt  oválisok olyan kisméretű családja, melyek szeparálják a sík egyeneseit? (Két egyenes szeparálva van, ha különböző oválisokat metszenek.)

Bőségreguláris gráfokról

Oct 21, György Kiss

We consider a new type of regularity we call edge-girth-regularity. An edge-girth-regular \((v,k,g,\lambda)\)-graph \(G\) is a \(k\)-regular graph of order \(v\) and girth \(g\) in which every edge is contained in \(\lambda\) distinct \(g\)-cycles. This concept is a generalization of the well-known \((v,k,\lambda)\)-edge-regular graphs (that count the number of triangles) and appears in several related problems such as Moore graphs and Cage and Degree/Diameter Problems. All edge- and arc-transitive graphs are edge-girth-regular as well. We derive a number of basic properties of edge-girth-regular graphs, systematically consider cubic and tetravalent graphs from this class, and introduce several constructions that produce infinite families of edge-girth-regular graphs. We also exhibit several surprising connections to regular embeddings of graphs in orientable surfaces.

Scattered alterek maximális dimenziója

Oct 14, Bence Csajbók

Legyen \(V\) egy GF\((q^n)\)-feletti \(r\)-dimenziós vektortér, \(n, r >1\), és legyen \(U\) a \(V\)-nek egy GF\((q)\)-altere. Az \(U\) altér "scattered", ha a \(V\) egydimenziós GF\((q^n)\)-altereit legfeljebb egydimenziós GF\((q)\)-alterekben metszi. Blokhuis és Lavrauw megmutatták, hogy scattered altér GF\((q)\)-feletti dimenziója legfeljebb \(rn/2\) lehet. Például az \(n=2\) esetben léteznek \(r\)-dimenziós scattered alterek, és ezek projektivizálás után a Baer-részgeometriáknak felelnek meg. Lavrauwtól származik egy konstrukció, ami páros \(r\) esetén minden \(n\)-re \(rn/2\)-dimenziós scattered alteret ad. Páratlan \(r\) és páros \(n\) esetén eddig csak bizonyos \(q, n\) párokra voltak konstruciók (Bartoli, Giulietti, Marino, Polverino), illetve nem konstruktív, \(rn/2\)-dimenziós scattered alterek létezését bizonyító eredmények (Blokhuis, Lavrauw). Előadásomban mutatok egy konstrukciót, ami páratlan \(r\),  páros \(n\) és bármely \(q\) esetén működik, tehát a Blokhuis-Lavrauw korlát éles valahányszor \(rn\) páros. Olga  Polverinóval és Giuseppe Marinóval közös munka.

Polinomok és a cap set probléma

Oct 7, Péter Pál Pach

Croottal és Levvel közösen megmutattuk, hogy \(\mathbb{Z}_4^n\) bármely (nemkonstans) háromtagú számtani sorozatot nem tartalmazó részhalmazának elemszáma legfeljebb \(c^n\) lehet, ahol \(c< 3.62\) explicit konstans, vagyis a csoport méretéhez viszonyítva exponenciálisan kicsi. Ezt megelőzően a legerősebb felső becslést Sanders adta: \(4^n/(n(\log n)^d)\), ahol \(d>0\). A bizonyításhoz a polinom-módszer egy új típusú változatát dolgoztuk ki. Ennek a módszernek az elmúlt hónapokban már számos további alkalmazása született, például segítségével hasonló becslés adható \(\mathbb{F}_q^n\) esetében is, és az Erdős-Szemerédi-féle napraforgósejtést is bebizonyították.

Extraordinary external talk at the Geometry Seminar of the Rényi Institute:
Polychromatic coloring and cover-decomposition problems for pseudohalfplanes and hemispheres

Sep 30, Dömötör Pálvölgyi (Rényi Institute, 14:15, Dog room or main lecture hall)

Konform geometriák modellezése valósok és véges testek felett

Sep 23, Máté Lehel Juhász (Rényi Institute)

Véges geometriák közül a véges projektív geometriák, illetve véges Möbius síkok ismertek. Mindkettőnek a kulcs eseteit lehetséges véges testek feletti algebrákkal modellezni. Felmerül a kérdés, hogy lehet-e más típusú véges geometriákat készíteni, mint például konform geometriákat.

A valós test feletti konform geometriák, mint a gömbi, az euklideszi és a hiperbolikus geometriák között mély összefüggések vannak, amit többnyire differenciálgeometriai úton vezetnek le. Emellet az egyik legfontosabb különbség a távolság mérésének jellege. Ez az összefüggés megfogalmazható tisztán lineáris algebrai eszközökkel.

Ezen az előadáson bemutatok egy olyan modellt, amivel levezethető egy tisztán algebrai távolságmérés és szögmérés fogalom, és rendszerezem a lehetséges geometriákat valósok és véges testek felett nem 2 karakterisztikára.

(Extending) arcs of vector spaces

Sep 16, Jan De Beule (Brussels)

Let \(V(n,q)\) be the \(n\)-dimensional vector space over the finite field \(F_q\). An arc is a set of vectors with the property that every subset of size \(n\), is a basis of the vector space. The MDS conjecture states an upper bound on the size of an arc. Some recent results using interpolation of polynomials and inclusion matrices will be discussed. This includes the approach to prove an upper bound on the size in particular cases, and a way to study extendability of arcs. The talk is based on ideas and work of Simeon Ball, including some joint work with him.

Program of 2016 Spring

On bisecants of Rédei type blocking sets + pizza

May 13, Bence Csajbók

If \(B\) is a minimal blocking set of size less than \(3(q+1)/2\) in PG\((2,q)\), \(q\) is a power of the prime \(p\), then Tamás Szőnyi's result states that each line meets \(B\) in 1 mod \(p\) points. It follows that \(B\) cannot have bisecants, i.e. lines meeting \(B\) in exactly two points. If \(q>13\), then there is only one known minimal blocking set of size \(3(q+1)/2\) in PG\((2,q)\), the so called projective triangle. This blocking set is of Rédei type and it has \(3(q-1)/2\) bisecants, which have a very strict structure. We use polynomial techniques to derive structural results on Rédei type blocking sets from information on their bisecants. We will also discuss connections with the direction problem.

Expander polinomok és alkalmazásaik

Apr 29, Norbert Hegyvári

Az előadáson prímtestbeli expander (nagyító) polinomokról és azok alkalmazásairól lesz szó. Az első explicit kétváltozós expandert Bourgain találta 2005-ben. Mutatunk expander polinomok egy végtelen osztályát, és megvizsgáljuk az expanzió mértékét. Megmutatjuk, hogy hogyan van kapcsolatban ez pl. Heisenberg-csoportok szorzathalmazaival. Végül Tao egy szép és mély eredményét ismertetjük (természetesen részletes bizonyítás nélkül), amelyik a tárgyhalmaz méretének bizonyos tartományának korlátozásában teljesen leírja az expander polinomokat.

Complex conference matrices and Equi-isoclinic sets of planes

Apr 8, Aart Blokhuis (TUE)

We construct an infinite family of complex conference matrices of odd order, and use them to produce maximal sets of equi-isoclinic planes in Euclidean space in the sense that they meet the upper bound by Lemmens and Seidel.

Classes and equivalence of linear sets in \(\mathrm{PG}(1,q^n)\)

Apr 1, Bence Csajbók (Second University of Naples)

The equivalence problem of \(\mathrm{GF}(q)\)-linear sets of rank \(n\) of \(\mathrm{PG}(1,q^n)\) will be investigated, also in terms of the associated variety, projecting configurations, \(\mathrm{GF}(q)\)-linear blocking sets of Rédei type, MRD-codes. Joint work with Olga Polverino and Giuseppe Marino.

Affin és biaffin síkok megoldó halmazai

Mar 18, Tamás Héger

Egy \(G\) gráfban egy \(S\) csúcshalmaz megoldóhalmaz (resolving set), ha \(G\) minden csúcsa egyértelműen azonosítható az \(S\)-beli csúcsoktól vett távolságai alapján. \(G\) legkisebb megoldóhalmazának méretét \(G\) metrikus dimenziójának hívják. R. F. Bailey vetette föl 2011-ben véges projektív síkok incidenciagráfjának vizsgálatát ebből a szempontból. Erre a kérdésre válaszoltunk Takáts Marcellával 2012-ben. Azóta Daniele Bartolival, Kiss Györggyel és Takáts Marcellával elkezdtük az affin es biaffin síkok metrikus dimenziójának meghatározását is. Egy biaffin sík (ezeket néha flag-típusú elliptikus szemisíknak is hívják) az a parciális lineáris tér, melyet egy affin síkbol kapunk egy párhuzamossági osztály egyeneseinek elhagyása után (pontokat nem törlünk). Az affin síkok esetében a kérdés egyszerűen visszavezethető a projektív síkok esetére; biaffin síkok esetében már nem látszik ilyen közvetlen kapcsolat. A folyamatban lévő kutatási eredményeinkről fogok beszámolni.

Transzverzálisok Latin mátrixokban

Mar 4, János Barát

Egy mátrix Latin tulajdonságú, ha soronként és oszloponként csupa különböző elem szerepel benne. Egy \(n\times n\)-es mátrix Latin négyzet, ha ugyanaz az \(n\) szimbólum szerepel minden sorban és oszlopban. Egy \(t\) méretű \(T\) halmaz parciális transzverzális, ha \(T\) elemei különböző sorokat, oszlopokat és szimbólumokat tartalmaznak. Ez transzverzális, ha mérete \(n\), azaz a négyzetes mátrix rendje. Ryser sejtése, hogy minden páratlan rendű Latin négyzetben van transzverzális. Páros \(n\)-re függetlenül Brualdi és Stein sejtése, hogy van \(n-1\) méretű parciális transzverzális.
Lesz történeti áttekintés. Utána megvizsgáljuk a fenti problémakört Latin tulajdonságú mátrixokra, ahol több mint \(n\) szimbólum van. Azt várjuk, hogy minél több szimbólum van, annál könnyebben lesz transzverzális. Akbari és Alipour definiálta \(a(n)\)-et mint a legkevesebb szimbólum egy \(n\times n\)-es általánosított Latin négyzetben, ami garantálja transzverzális létezését; azaz tetszőleges olyan \(n\times n\)-es általánosított Latin négyzetben van transzverzális, mely legalább \(a(n)\) szimbólumot tartalmaz.
Akbari és Alipour sejtése, hogy \(a(n) \leq n^2/2\), és hogy nincs olyan \(c\) konstans, melyre \(a(n) \leq n+c\) minden \(n\)-re. Ezekre mutatunk valamit.

The minimum number of vertices in uniform hypergraphs with large domination number

Feb 26, Balázs Patkós

The domination number \(\gamma(\mathcal{H})\) of a hypergraph \(\mathcal{H}=(V(\mathcal{H}),E(\mathcal{H}))\) is the minimum size of a subset \(D\subseteq V(\mathcal{H})\) of the vertices such that for every \(v\in V(\mathcal{H})\) there exist a vertex \(d \in D\) and an edge \(H\in E(\mathcal{H})\) with \(v,d\in H\). We address the problem of finding the minimum number \(n(k,\gamma)\) of vertices that a \(k\)-uniform hypergraph \(\mathcal{H}\) can have if \(\gamma(\mathcal{H})\ge \gamma\) and \(\mathcal{H}\) does not contain isolated vertices. We prove that \(n(k,\gamma)=k+\Theta(k^{1-1/\gamma})\) and also consider the \(s\)-wise dominating and the distance-\(\ell\) dominating version of the problem. In particular, we show that the minimum number \(n_{dc}(k,\gamma, \ell)\) of vertices that a connected \(k\)-uniform hypergraph with distance-\(\ell\) domination number \(\gamma\) can have is roughly \(\frac{k\gamma \ell}{2}\). One of the upper bounds uses finite geometries. Joint work with Csilla Bujtás, Zsolt Tuza, and Máté Vizer.

Dominating sets of PG\((2,q)\) + A finite geometric analogue of the Erdős-Stone theorem

Feb 19, Tamás Héger + Zoltán L. Nagy

Genocchi numbers of the second kind

Feb 12, Aart Blokhuis

Program of 2015 Fall

The panciclycity of finite planes - part II + pizza

Dec 12, Szabolcs Levente Fancsali

Felix Lazebnik et. al. konstruktív módon igazolták egy 2013-as munkájukban, hogy minden páros, legalább 6 és legfeljebb \(2(q^2+q+1)\) hosszúságú kör előfordul minden \(q\)-adrendű véges projektív sík illeszkedési gráfjában. Speciálisan ezek a gráfok Hamiltoniak. A testre épített esetben a Singer ciklus bizonyítja Hamilton-kör létezését, az általános esetben ez régóta nyitott kérdés volt. Az előadáson ezt a konstrukciót fogom ismertetni projektív síkokra, az affin síkokra mutatott konstrukció felhasználásával.

The panciclycity of finite planes - part I

Nov 27, Szabolcs Levente Fancsali

Felix Lazebnik et. al. konstruktív módon igazolták egy 2013-as munkájukban, hogy minden páros, legalább 6 és legfeljebb \(2(q^2+q+1)\) hosszúságú kör előfordul minden \(q\)-adrendű véges projektív sík illeszkedési gráfjában (azaz ezek a gráfok pánciklikusak). Speciálisan ezek a gráfok Hamiltoniak. A testre épített esetben a Singer ciklus bizonyítja Hamilton-kör létezését, az általános esetben ez régóta nyitott kérdés volt. Az előadáson az affin síkok pánciklikusságát fogom bizonyítani, a projektív síkok pánciklikusságát a következő alkalommal tárgyaljuk.

What may be similar to the Paley graph in even characteristic?

Nov 20, János Barát

The Paley graph is a well-known self-complementary pseudo-random graph, defined over a finite field of odd order. We describe an attempt at an analogous construction using fields of even order. Some properties of the graph are noted, such as the existence of a Hamiltonian decomposition. The talk is based on a work of Andrew Thomason.

No seminar

Nov 6

Break

Oct 30

National holiday

Oct 23

Kis domináló halmazok struktúrája véges geometriákban

Oct 16, Zoltán Lóránt Nagy

Egy \(G\) gráfban egy \(D\) csúcshalmaz domináló, ha minden \(D\)-n kívül eső csúcsnak van szomszédja \(D\)-ben. Legyen most \(G\) egy tetszőleges \(q\) rendű véges projektív sík illeszkedési gráfja. Azt a kérdést vizsgáljuk, hogy ebben a gráfban milyen szerkezetű lehet egy kicsi domináló halmaz. Egy lefogó ponthalmaz és egy lefedő egyeneshalmaz uniója természetesen adódó példa domináló halmazra. Ha a világ szép, előzetes várakozásunk az lehet, hogy a kis domináló halmazok ilyen, vagy ehhez nagyon közeli struktúrák. (Vagyis van stabilitás, ahogy a lefogó halmazoknál is.) Az előadásban efféle eredményt igazolunk. Héger Tamással közös munka.

Néhány algebrailag definiált gráf unicitásáról

Oct 9, Tamás Héger

The classical result of Feit and Higman

Oct 2, Szabolcs Levente Fancsali

In the talk the classical result of Feit and Higman will be introduced, which says that no generalized \(n\)-gon exists unless \(n\in\{3,4,6,8,12\}\).

Program of 2015 Spring

Extra seminar:

New results on constant dimension random network codes

Jun 05, Prof. Leo Storme (University of Gent, Belgium)

Két miniatűr gráfelmélethez kapcsolódóan + pizza

May 15, Zoltán Loránt Nagy

Az alkalom első felében egy Erdős - Szemerédi tétel kvantitatív változatát mutatnám be, ami arról szól, hogy egy \(p\) sűrűségű gráfban van - \(p\)-függően - elég nagy  klikk vagy üres részgráf. A bizonyítás főszereplője a Zarankiewicz-számok Culik-féle éles korlátja lesz. Az eredmény korábbi Ramsey-típusú kérdésemnél bizonyult hasznosnak. A második felében - ha még nem pizzázunk-, egy másik, nyitott Erdős-problémáról ejtenék szót, és kissé a kutatószemináriumi hangvételt felvetve megosztanám pár gondolatomat, hogyan lehetne polinomok segítségével  esetleg részeredményeket elérni.

Break

May 8

Holiday

May 1

No seminar

Apr 24

No seminar

Apr 17

On the size of value sets of polynomials over finite fields

Apr 10, Tamás Héger

Véges testek fölötti polinomok értékkészletét többen vizsgálták. Cusick és Rosendahl a \(\mathrm{GF}(q^2)\) test fölötti, \(f_a(x)=x^{a}(x+1)^{q-1}\) alakú polinomokkal foglalkoztak. Ezek értékkészletének méretére leginkább páros karakterisztika esetén vannak algebrai eszközöket hasznaló eredmények bizonyos \(a\) értekekre. Az előadásban főként az \(a=-1\) esetet vizsgáljuk, páratlan \(q\) esetén. Jan De Beule-vel, Szőnyi Tamással és Geertrui Van de Voorde-vel közös munkánk során kiderült, hogy \(f_{-1}(x)\) értékkészlétenek mérete meghatározható geometriai úton: bizonyos \(\mathrm{PG}(2,q^2)\)-beli Baer-részsíkok metszeteit (pontosabban, bizonyos Hall-síkbeli ponthalmaznak az egy párhuzamossági osztályba eső szelőinek számát) vizsgálva.

Spring break

Apr 3

On the size of semiovals in planes of square order

Mar 27, György Kiss

On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method

Mar 20, Balázs Patkós

We study the function \(M(n,k)\) which denotes the number of maximal \(k\)-uniform intersecting families over an \(n\)-element ground set. Improving a bound of Balogh et al. on \(M(n,k)\), we determine the order of magnitude of \(\log M(n,k)\) by proving that for any fixed \(k\), \(M(n,k)=n^{\theta\left(\binom{2k}{k}\right)}\) holds. Our proof is based on Tuza's set pair approach. The main idea is to bound the size of the largest possible point set of a cross-intersecting system. We also introduce and investigate some related functions and parameters. This is a joint work with Zoltán L. Nagy.

Flamand mesterek regulája, mely szigorúan megszabja minden \(q\)-rendű projektív részegyenesnek, hogy hány közös pontja is lehessen egy \(q\)-rendű projektív lineáris halmazzal.

Mar 13, Szabolcs L. Fancsali

Múlt félévben Sziklai Péter elmondta annak bizonyítását, hogy egy \(q\)-lineáris (3-rangú) golfütőnek (avagy Club-nak) 0, 1, 2 vagy 3 közös pontja lehet minden olyan \(q\)-rendű projektív lineáris részegyenessel, amit a golfütő nem tartalmaz teljesen.
Geertrui Van de Voorde és Michel Lavrauw (egy általuk tévesen hibásnak vélt bizonyítást kijavítani akarván) ezt a tételt általánosították: bebizonyitották, hogy minden \(k\)-rangú, \(q\)-lineáris halmaznak legfeljebb \(k\) közös pontja lehet egy általa nem tartalmazott \(q\)-rendű részegyenessel.
Ezt a bizonyítást fogom ismertetni, és előtte felidézem a hozzá szükséges fogalmakat, a lineáris halmazok különféle reprezentációit, és a Segre-varietások regulusait.

No seminar

Mar 06

Point sets from strongly regular graphs

Feb 27, Jan De Beule

We study weighted intriguing sets of finite classical polar spaces. Such point sets are coming from the eigenspaces of the point graph of the underlying geometry which is strongly regular. Intersection properties of tight sets and \(m\)-ovoids (both examples of intriguing sets), can be studied relatively easy. This motivates the construction of particular examples with the aim to proof e.g. non-existence results for ovoids of finite classical polar spaces. This is joint work with John Bamberg (Perth) and Ferdinand Ihringer (Giessen).

A finite version of the Kakeya problem

Feb 20, Aart Blokhuis

Joint work with Simeon Ball and Diego Domenzain. Let \(L\) be a set of lines of an affine space with a prescribed set of directions \(D\), and let \(S\) be a set of points with the property that every line of \(L\) is incident with at least \(N\) points of \(S\), in other words \(S\) is an \(N\)-fold blocking set for the set \(L\).
We give a geometric construction of a set of lines \(L\), where \(D\) is an \(N^{n-1}\) grid with \(S\) of size \(2(N/2)^n\). Following Dvir's proof of the Kakeya conjecture, we prove a lower bound on the size of \(S\) dependent on the ideal generated by the homogeneous polynomials vanishing on \(D\), and then improve the lower bound on \(S\) to \((N/2)^n\) in the case that \(D\) is a grid, following the idea of using multiplicities by Dvir, Kopparty, Saraf and Sudan.

Program of 2014 Fall

12 Dec: Gy. Kiss: Véges terek színezései abstract
05 Dec: Z. L. Nagy: Független és többszörösen domináló halmazok abstract
Special seminar on 25 Nov, Southern Building Room 3.518:
J. De Beule: Introduction to FinInG, a new GAP package for studying Finite Incidence Geometries
21 Nov: J. De Beule: A new infinite family of tight sets of the hyperbolic quadric Q^+(5,q) abstract
14 Nov: G. Gévay: Geometriai konfigurációk abstract
7 Nov: A. Blokhuis: Reducing the discrete diameter of a point set abstract
24 Oct, 1 Nov: break
17 Oct: G. Nagy: Hermite-féle algebrai hibajavító kódok abstract
10 Oct: Z. Blázsik: Egy reguláris gráf spektruma meghatározza-e azt, hogy a gráfban van-e teljes párosítás? and Gy. Kiss: Mesék szabályos és féligszabályos politopokról abstracts
3 Oct: P. Sziklai: Résztest felett lineáris ponthalmazok projektív terekben abstract
26 Sept: J. Barát: Gráfok élfelbontásai abstract
12 Sept: B. Csajbók: On the minimal number of odd-secants of small point sets in PG(2,q), q odd abstract

Program of 2014 Spring

28 Febr: J. Barát: Ryser's conjecture for intersecting hypergraphs
7 March: A. Blokhuis: Maximal cocliques in the Kneser graph on point-plane flags in PG(4,q)
14 March: G. Nagy: Multiplication group of finite semifields and the solution of a problem of Drapal abstract
21 March: B. Csajbók: Some Segre type results concerning small semiovals in PG(2,q) abstract (in Hungarian)
4 Apr: T. Héger: Some results on blocking sets abstract (in Hungarian)
25 Apr: Z. Blázsik: The characterization of multiple (n-k)-blocking sets in projective spaces of non-square order abstract (in Hungarian)
16 May: Gy. Kiss: On achromatic and pseudoachromatic indices of affine spaces abstract

Program of 2013 Fall

4 Sept: D. Bartoli (Perugia): Notes on semifields
5 Sept: F. Pambianco (Perugia): Symmetric algebraic curves
20 Sept: T. Szőnyi: Incidences in finite planes
27 Sept: T. Héger: Generalized polygons as extremal graphs abstract (in English)   abstract (in Hungarian)
4 Oct: P. Sziklai: Lines generating hyperplanes
11 Oct: G. Nagy (Szeged): Projective embeddings of k-nets abstract
18 Oct:
25 Oct: A. Blokhuis: On the Alon-Tarsi problem
8 Nov: Gy. Kiss: On Moore graphs abstract
15 Nov: Z. L. Nagy: Search with Hamming-sphere search sets abstract
22 Nov: Sz. L. Fancsali: Explicit subspace-designs abstract
29 Nov: K. Gyarmati: Exponential sums and multiplicative characters abstract
6 Dec: G. Kun: Cops and robbers on random graphs abstract
13 Dec: B. Csajbók: Rhombus tilings abstract

Program of 2013 Spring

15 Febr: A. Blokhuis: Flat-containing and shift blocking sets abstract (abstract in pdf)
22 Febr: B. Csajbók: Small semiarcs with a long secant in PG(2,q) abstract
1 March: C. Rubio: On m-factorizations of complete multigraphs and finite projective spaces abstract (abstract in pdf)
8 March: T. Szőnyi: A remark on the blocking sets of Hermitian curves, and T. Héger: Two remarks on the problem of Zarankiewicz
22 March: Sz. L. Fancsali: Art of Schubert (Schubert-calculus and Grassmann-varieties)
5 Apr: Sz. L. Fancsali: Art of Schubert II. (Schubert-calculus and Grassmann-varieties)
12 Apr: A. Blokhuis: Characterization of a graph by its spectrum abstract, and A. Sonnino: Arcs in Galois geometries and their applications abstract
19 Apr: B. Patkós: Searching in vectorspaces abstract
26 Apr: J. Ruff: Integral automorphisms of affine planes over finite fields
3 May: P. Csikvári: Homomorphisms between trees II. abstract
17 May: S. Bajric: On Generalized Bent Functions With Dillon's Exponents abstract

Program of 2012 Fall

28 Sept: Gy. Kiss: 2-semiarcs of small size on Desarguesian planes
5 Oct: A. Blokhuis: Codes and polynomials 1
12 Oct: A. Blokhuis: Codes and polynomials 2
19 Oct: T. Héger: The upper chromatic number of PG(2,q) and small double blocking sets abstract
26 Oct: Gy. Károlyi: A problem regarding extremal set systems
9 Nov: P. Sziklai: The direction problem and its generalizations
16 Nov: cancelled
23 Nov: T. Szonyi: Blocking sets in unitals
30 Nov: P. Csikvári: Benjamini-Schramm continuity of root moments of graph polynomials, and Z. L. Nagy: On the density Ramsey-question, and Gy. Kiss: Coloring of projective planes
7 Dec: Sz. L. Fancsali: The connection of network coding and finite geometries, with emphasis on Grassmann codes
14 Dec: M. D. Boeck: The largest Erdos-Ko-Rado in finite projective and polar spaces

Program of 2012 Spring

17 Febr: A. Blokhuis: Small Kakeya sets
24 Febr: I. Kovacs: The smallest cyclic non-Schur group of odd order
2 March: B. Csajbok: Perspective point sets and their applications
9 March: T. Heger: The resultant method
23 March: B. Kuzman: On elementary-abelian covers of doubled cycles
30 March: G. Korchmaros: Unitals in PG(2,q^2) and strongly regular graphs
13 Apr: J. D. Beule: On (recent) results towards the MDS-conjecture
20 Apr: P. Csikvari: Homomorphisms between trees
27 Apr: J. D. Beule: Cameron-Liebler line classes in PG(3,q)
4 May: P. Levay: Black hole entropy and finite geometries
18 May: pizza
8 June: G. Marino: Ovoidal blocking sets and maximal partial ovoids of Hermitian varieties

Program of 2011 Fall

23 Sept: Peter Sziklai: Directions, extendability, algebraic hypersurfaces
30 Sept: Zoltan Lorant Nagy: On a question of Balazs Patkos
7 Oct: Marcella Takats: Resolving sets in finite projective planes
14 Oct: Tamas Heger: Semi resolving sets in finite projective planes
21 Oct: cancelled
28 Oct: Aart Blokhuis: Maximal cocliques in generalized Kneser graphs: (infinitely many) generalizations of the Erdos-Ko-Rado Theorem
11 Nov: Ph. D. defence of Peter Csikvari
18 Nov: Gyorgy Kiss: Weakly associative lattices and projective planes
25 Nov: B. Csajbok: Linear subspaces with large subsets closed to inversion
2 Dec: G. Keri: Surjective codes asymptotically

Program of 2011 Spring

25 Febr: Z. L. Nagy: On the sumset partition problem
4 March: Sz. L. Fancsali:
11 March: M. Takats: A generalization of the direction problem
18 March: I. Kovacs: On covering systems of finite abelian groups
25 March: Gy. Károlyi: On the existence of pairs with prescribed distance
1 Apr: A. Blokhuis: On the uniqueness of the Brouwer60 graph
8 Apr: C. Kiss-Toth: Sudoku and finite geometries
15 Apr: T. Heger: The Lemma of Tangents reformulated (article of Kris Coolsaet)
29 Apr: T. Szonyi: On small blocking sets
6 May: J. Ruff: Rose-window graphs
20 May: N. Harrach: Almost blocking sets and almost coverings and G. Meszaros: Arcs on Hall-planes

Program of 2010 Fall

24 Sept: B. Csajbok: Semiovals and semiarcs on finite planes
1 Oct: I. Kovács: On regular Cayley maps on dihedral groups
8 Oct: N. Harrach: On t-fold (n-k)-blocking sets of PG(n, q)
15 Oct: Gy. Kiss: Semiovals which are constructed as the union of conics
22 Oct: A. Blokhuis: Maximal cocliques of the Kneser-graph of point-hyperplane flags in projective spaces
5 Nov: T. Héger: Regular configurations in projective planes
12 Nov: J. D. Beule: Small (n-1)-covers of the polar spaces Q+(2n+1,q) and H(2n+1,q^2)
19 Nov: P. Csikvári: Polynomial and multilinear methods
26 Nov: P. Sziklai: About the Nullstellensatz
3 Dec: M. Takats: Maximal integral point sets in affine planes over finite fields
10 Dec: G. V. d. Voorde: Stopping sets in LDPC codes and sets without tangents in finite projective planes
17 Dec: Z. L. Nagy: Permutations over cyclic groups

Program of 2010 Spring

Febr: G Nagy: On the prime power conjecture
26 Febr: N. Harrach: t-fold blocking sets
5  March: Sz.L.Fancsali: Direction sets
12 March: Gy. Kiss: The mutual position of conics
26 March: Gy. Kiss: MES
9 Apr: T. Héger: Zarankiewicz's problem (a paper of Steven Roman)
16 Apr: P. Sziklai: Directions and perfect sumsets
30 Apr: Angelo Sonnino: Projective k-arcs and 2-level sharing schemes and G. Korchmaros: 3-nets embedding in a projective plane
7 May: A. Blokhuis: On the structure of 3-nets embedded in a projective plane
14 May: Leo Storme: Minimal codewords in Reed-Muller codes
8 Jun: T. Penttila: Groups of Lie type as a source of finite geometry

Program of 2009 Fall

18 Sept: T. Szőnyi: Hilton-Milner theorems for vector spaces
25 Sept: N. Harrach: On high dimensional blocking sets
2 Oct: T. Szőnyi: On the chromatic number of the Kneser graph of parameter n=2
9 Oct: Gy. Károlyi: The recent proof of the Snevily conjecture
16 Oct:T. Szőnyi: On the chromatic number of the Kneser graph of parameter n=2k, cont'd
6 Nov: G. Kéri: On orthogonal arrays, covering arrays and the nonlinear MDS conjecture
13 Nov:  Jan De Beule (Gent, Belgium): On (Partial) ovoids and (partial) m-ovois of Q-(5,q)
20 Nov:  Jan De Beule
27 Nov:  Valentina Pepe (Gent, Belgium): Erdos-Ko-Rado theorems for dual polar spaces
4   Dec:  Anja Hallez (Gent, Belgium): Sets of generators blocking all generators in finite classical polar spaces
11 Dec:  P. Csikvári: Independent sets in graphs

Program of 2009 Spring

20 Febr: G. Kéri
27 Febr: conference
March: G. Kéri
13 March: Gy. Kiss: On the size of semiovals
20 March: P. Sziklai: Codewords of small weight
27 March: P. Sziklai, cont'd; M. Takats: Generalized caps
3 Apr: Z.L. Nagy
17 Apr: cancelled
24 Apr:  Aart Blokhuis
15 May: P. Csikvári: On a proof of Burnside's theorem

Program of 2008 Fall

19 Sept: A. Gács: Extendability of MDS codes
3 Oct: G. Nagy:  Bol-loops of expontent 2
10 Oct: S. Ball (UPC, Barcelona): Codes, bounds and blocking sets
17 Oct: Gy. Károlyi: Exterior algebra methods
7 Nov: Jan De Beule (Gent): Particular facts about finite classical generalized quadrangles
14 Nov: B. Montagh: Graph constructions
21 Nov: G. Pluhár: Islands on the triangular lattice
28 Nov: M. Korom: Blocking lines exterior to a quadric, I
Dec: S. Vidor: Blocking lines exterior to a quadric, II
12 Dec: A Gács: On the discrete Kakeya problem

Program of 2008 Spring

15 Febr: A. Gacs: A 70 years old problem
22 Febr: Gy. Kiss: Sudoku and finite geometry
29 Febr: K. Horvath: Norm graphs
7 March: A Gacs: Embeddings of partial projective planes
14 March: B. Csajbok: Upper bounds on the number of lines in maximal cliques
28 March: Leo Storme (Gent): Blocking sets in PG(3,q)
4 Apr: Sz. Fancsali: On minimal t-fold blocking sets
11 Apr:  I. Stuhl: Steiner loops and their small extensions
18 Apr: E. Adamcsek: 1- and t-factorisations of the complete graph
25 Apr: Z. Gyenis: Constructions of maximal arcs
16 May: B. Csajbok: Maximal intersecting systems

Program of 2007 Fall

21 Sept: T. Heger:  Configurations
5 Oct: K. Kutnar: A complete classification of cubic symmetric graphs of girth 6
12 Oct: P. Csikvari: Line-free sets in AG(n,3) and the SET game
19 Oct: P. Csikvari: Sumsets with square elements I.
26 Oct: P. Csikvari: Sumsets with square elements II.
9 Nov: N. Harrach: (New) blocking sets in AG(2,q)
16 Nov: S. Miklavic: Consistent polygons in configurations
23 Nov: M. Weiner: Quantum information theory and finite projective planes
30 Nov: Gy. Kiss: On semiovals
7 Dec: P. Sziklai: The punctured Nullstellensatz
14 Dec: T. Szonyi: Codes and curves

Program of 2007 Spring

16 Febr: Gy. Kiss: Large Cayley graphs with given degree and diameter
23 Febr: Sz. Fancsali: Minimal weight words of codes of projective planes
2 March: Zs. Tuza: Hypergraph coloring and projective planes
9 March: A Gacs: Directions in the plane and generalizations
23 March: P. Sziklai: On Vandermonde sets
30 March: Z.L. Nagy: Directions in the 3-space
13 April: B. Acs: The Hoffman-Singleton paper
20 April: D. Pinter: Groebner bases and the Babai-Frankl conjecture I.
27 April: D. Pinter: Groebner bases and the Babai-Frankl conjecture II.
11 May:
18 May: T. Heger: Extremal graphs and finite geometries

Program of 2006 Fall

29 Sept: A Gacs: On random constructions
6 Oct: Gy. Kiss: Semiovals
13 Oct: Aart Blokhuis: Button madness
27 Oct: A Gacs & T. Szonyi: Directions determined by a pointset in AG(2,q)
10 Nov: A. Gacs: continued
17 Nov: Jan De Beule (Gent): Generalized quadrangles 1
24 Nov: Jan De Beule (Gent): Generalized quadrangles 2
1 Dec: Jan De Beule (Gent): Generalized quadrangles 3
8 Dec: Simeon Ball (Barcelona, UPC)
15 Dec: A. Szekér

Program of 2006 Spring

24 Febr: Gy. Kiss: 1-factorisations
3 March: A. Gacs: Introduction to polar spaces 1
10 March: Zs. Weiner: Introduction to polar spaces 2
24 March: Zs. Weiner: Polar spaces and generalized quadrangles
31 March: Gabor Bartok
7 April: Szabolcs Fancsali
28 April: Zs. Weiner: Generalized quadrangles and ovoids 1
12 May: Gyula Karolyi
19 May: Zs. Weiner: Generalized quadrangles and ovoids 2

Program of 2005 Fall

23 Sept.: Istvan Kovacs: On nonexistence of semiovals
30 Sept.: Tamas Szonyi: Stability of blocking sets
14 Oct.: Andras Gacs: Point sets with 0 mod p intersections
21 Oct.: Zsuzsa Weiner: Stability of even pointsets
28 Oct.: Gyula Karolyi: Combinatorial Nullstellensatz-like results
1 Nov.: Tamas Szonyi: Cyclic arcs
18 Nov.: Jan De Beule: On maximal partial spreads of Hermitian varieties
25 Nov.: Aart Blokhuis: TBA
2 Dec.: Andras Gacs: Applications of the combinatorial Nullstellensatz
9 Dec.: Gyorgy Kiss: A geometric construction of large vertex transitive graphs
16 Dec.: Peter Sziklai: TBA + pizza

Program of 2005 Spring

Febr. 18.: Rita Vincenti: Characterizations of (varieties and) codes from the Tallini point of view
Febr. 25.: Gacs Andras: Redei polynomials in dim>2
March 4.: Nagy Gabor: Lines on algebraic surfaces
March 11.: Weiner Zsuzsa: Extendability of linear codes, and blocking seta
March 18.: Szonyi Tamas: On the size of an independent set in the Erdos-Renyi graph
Apr. 1.: Szabo Csaba: Algebraic properties of a geometrical configuration
Apr. 8.: Hendrik Van Maldeghem: Geometries from certain doubly transitive permutation groups
Apr. 15.: Szonyi Tamas: Applications of algebraic curves I.
Apr. 22.: Szonyi Tamas: Applications of algebraic curves II.
Apr. 29.: Szonyi Tamas: Applications of algebraic curves III.
May 6.: Aart Blokhuis: Constructions of Bipartite Graphs from Finite Geometries
May 20.: Mengyan Csaba: TBA + pizza

Program of 2004 Fall

Sept. 24: Sziklai Peter: (Partial) flocks of cones
Oct. 1: Szonyi Tamas: Bounds on arcs of projective planes
Oct. 8: Kovacs Istvan: Cayley graphs of non-commutative groups
Oct. 15: Szonyi Tamas: The Segre-Korchmaros theorem and its applications
Oct. 22: -- continued --
Oct. 29: Gacs Andras: Regular semiovals
Nov. 5: NO SEMINAR
Nov. 12: Leo Storme (Gent): Shortened incidence matrices of PG(2,p)
Nov. 19: Aart Blokhuis (Eindhoven)
Nov. 26: Stefan Dodunekov: Codes and geometry
Dec. 3: Gyorey Bernadett: Planar functions
Dec. 10: Gacs Andras: Applications of finite geometry (in graph theory)
Dec. 17: -- continued --

Program of 2004 Spring

febr. 20: Sziklai Peter: On small blocking sets
febr. 27: NO TALK
marc. 5: Sziklai Peter: On small blocking sets
marc. 12: Sziklai Peter: On small blocking sets
marc. 19: Nagy Gabor: Codes and Moufang loops
apr. 16: Szonyi Tamas: A paper of Tallini
apr. 23: Fancsali Szabolcs: Segre varieties
apr. 30: Ruff Janos: Semiovals of index 3

Program of 2003 Fall

19 Sept: Szonyi Tamas: n-e.c. graphs and affine planes
26 Sept: Szonyi Tamas: Flocks of cones: star flocks
3 Oct: Szonyi Tamas: Flocks of cones: star flocks (cont'd)
10 Oct: Gacs Andras: Introduction to ovoids, I
31 Oct: Gacs Andras: Introduction to ovoids, II
7 Nov: Sandy Ferret: Whether caps are parts of ovoids
14 Nov Patrick Govaerts: Mixed partial spreds and MAXMOLS
21 Nov Simeon Ball: Permutation polynomials arising from spreads
28 Nov Patrick Govaerts: Applications of Ball's 1 mod p result for ovoids of Q(4,q)
5 Dec Kovacs Istvan: Some problems related to Schur rings
12 Dec Weiner Zsuzsa: SETs and spreads

Program of 2003 Spring

28 Febr: Szonyi Tamas: On the number of lines meeting a (q+2)-set
7 March: Aart Blokhuis: External points determining passant lines
14 March: Aart Blokhuis: On blocking sets of size 3(p+1)/2
21 March: Szonyi Tamas: t-fold blocking sets
28 March: Szonyi Tamas: -- continued --
4 Apr: Gacs Andras: Planar functions
11 Apr: Kiss Gyorgy: Semiovals with a large collinear subset
18 Apr: SPRING HOLIDAYS
25 Apr: Kovacs Istvan: Circulant graphs on 2^m points, m is up to 5
2 May: NO SEMINAR
9 May: NO SEMINAR
16 May: Weiner Zsuzsa: On blocking sets

Program of 2002 Fall

20 Sept : Alessandro Siciliano: Flocks of hyperbolic quadrics
27 Sept : Szonyi Tamas: Flocks, herds and clans
4 Oct: Kiss Gyorgy: On quadratic surfaces
11 Oct: Szonyi Tamas: On quadratic surfaces, continued
18 Oct: Nagy Gabor: The geometry of orthogonal groups
25 Oct: Gacs Andras: Line-sets and spreads in PG(3,q)
1 Nov: NO SEMINAR
8 Nov: Gacs A.-Szonyi T.-Weiner Zs.: Large minimal blocking sets in planes of non-square order
15 Nov: Leo Storme: Codes meeting the Griesmer-bound and minihypers
22 Nov: Nagy Gabor: Extra-special groups and loops
29 Nov: Aart Blokhuis: Small additive quaternary codes and linesets in PG(n,2)
6 Dec: Kovacs Istvan: On the properties of the Paley graph
13 Dec: Pinter Domotor: Secret-sharing schemes

Program of 2002 Spring

22 Feb P 13.30-15.00 Dragan Marusic (Ljubljana)
25 Feb H 15.30-17.00 Sziklai Peter
1 Mar P !!! 13.30-15.00 Tichler Krisztian
11 Mar H 15.30-17.00 Szonyi Tamas
22 Mar P 13.30-15.00 instead: march 18 H 15.30-17.00: Korchmaros Gabor
25 Mar H 15.30-17.00 SPRING HOLIDAYS
5 Apr P 13.30-15.00 Szonyi Tamas
8 Apr H 15.30-17.00 Revai Nora
19 Apr P 13.30-15.00 Weiner Zsuzsa
22 Apr H 15.30-17.00 Weiner Zsuzsa
3 May P 13.30-15.00 Kiss Gyorgy
6 May H 15.30-17.00 Ruff Janos
17 May P 13.30-17.00 Simeon Ball