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 2019 Spring


Klikkszám becslése lineáris programozással

Maj 17, Ákos Beke (University of Pécs)

Kombinatorikai optimalizálási problémák sok esetben átfogalmazhatók 0-1 lineáris programozási feladatra. Egy gráf klikkszámának meghatározására az egyik ismert módszer az élátfogalmazás, ahol a komplementer gráf élei határoznak meg lineáris egyenlőtlenség feltételeket, ez a csúcsok számában négyzetes feltételt tartalmaz.
Előadásomban két olyan átfogalmazást ismertetek, amelyekben a feltételek száma megegyezik a csúcsok számával, továbbá ezen átfogalmazások két lehetséges megszorításáról lesz szó, amelyek valós relaxált esetén jobb felső korlátot eredményeznek a klikkszámra.
Közös munka Szabó Sándorral és Zaválnij Bogdánnal.

Eötvös & Pázmány Day - university break

Maj 10

Határozatlansági egyenlőtlenségek a véges síkon

Maj 03, András Biró (Rényi Institute)

Egy véges Abel-csoporton adott, nem azonosan eltűnő komplex függvény tartója és a Fourier-transzformáltjának a tartója nem lehet egyszerre nagyon kicsi: a két tartó elemszámának a szorzata legalább akkora, mint a csoport elemszáma. Ennek az ún. "határozatlansági relációnak" a lehetséges javításáról lesz szó egy speciális csoporton: egy prímelemű csoport saját magával vett direkt szorzatán.

Generalised KM-arcs (joint work with Bence Csajbók)

Apr 26, Zsuzsa Weiner

This talk is a continuation of the last seminar held by Bence. But do not worry :), I will repeat definitions and main ideas.
At the previous seminar Bence introduced three possible generalisations of KM-arcs (which I will quickly refresh) and also showed couple of examples of them. Then he proved some nice properties of them. Using that result (again which will be refreshed) and stability result on \(k \mod p\) multisets (which is a joint work with Tamás Szőnyi), I will prove some characterization type results on generalised KM-arcs.

Easter break - no seminar

Apr 19

Generalised KM-arcs (joint work with Zsuzsa Weiner)

Apr 12, Bence Csajbók

A KM-arc of type \((0,2,t)\) is a point set \(S\) of a finite projective plane of order \(q\) such that each point \(Q\) of \(S\) is incident with a unique line meeting S in t points and the other lines incident with \(Q\) meet \(S\) in two points. These objects have been studied first by Korchmáros and Mazzocca in 1990, that is why nowadays they are called KM-arcs. KM-arcs exist only for \(q\) and \(t\) even and they have been studied mostly in Desarguesian planes, where Gács and Weiner proved that the \(t\)-secants of a KM-arc are concurrent, their common point is called a nucleus.

In this talk we introduce the following three generalisations of KM-arcs:

  • A generalised KM-arc of type \((0,m,t)\) is a point set \(S\) of a finite projective plane of order \(q\) such that each point \(Q\) of \(S\) is incident with a unique line meeting \(S\) in \(t\) points and the other lines incident with \(Q\) meet \(S\) in \(m\) points.
  • A \(\mod p\) generalised KM-arc of type \((0,m_p,t_p)\) is a point set \(S\) of a finite projective plane of order \(q=p^n\) such that each point \(Q\) of \(S\) is incident with a unique line meeting \(S\) in \(t \mod p\) points and the other lines incident with \(Q\) meet \(S\) in \(m \mod p\) points.
  • A \(\mod p\) generalised KM-arc is a point set \(S\) of a finite projective plane of order \(q=p^n\) such that for each point \(Q\) of \(S\) there exists an integer \(m_Q\) such that all but at most one of the lines incident with \(Q\) meet \(S\) in \(m_Q \mod p\) points.

At the first part of the talk I will present various examples of these objects, some of them are also related to the Dirac-Motzkin conjecture on the minimum number of lines meeting an \(n\)-set of the real projective plane in exactly two points. Next I will show some combinatorial results and characterisations. Then, by using Rédei polynomials, I will show that whenever \(p\) is not a divisor of \(m-t\), then the \(m \mod p\) secants have a nucleus, more precisely: let \(r\) be a line meeting a \(\mod p\) generalized KM-arc of type \((0,m_p,t_p)\) in \(m \mod p\) points, then the \(t \mod p\) secants meeting \(S\) in \(r\) are concurrent. This result can be viewed as a generalisation of the fact that an affine \((q-1)\)-set can be extended into an affine \(q\)-set such that the two point sets determine the same set of directions (this was proved first by Blokhuis and then generalized for smaller point sets by Szőnyi and by Sziklai).

The fact that the \(m \mod p\) secants have a nucleus turned out to be very useful in the characterisation of \(\mod p\) generalised KM-arcs of type \((0,m_p,t_p)\). Combining this result with results on the stability of \(k \mod p\) multisets by Szőnyi and Weiner, we were able to describe all generalised KM-arcs of type \((0,m,t)\) when \(p\) does not divide \(m-t\). The proof of this result together with some further characterisations for \(\mod p\) generalised KM-arcs of type \((0,m_p,t_p)\) will be presented by Zsuzsa Weiner in a future seminar.

Többszörösen lefogó ponthalamzok felbontásáról

Mar 29, Tamás Héger

\(\mathrm{PG}(n,q)\) \(t\)-szeres \((n-k)\)-lefogó ponthalmaza olyan \(B\) ponthalmaz, amely minden \((n-k)\) kodimenziós, azaz \(k\) dimenziós alteret legalább \(t\) pontban metsz. Ezt definiálhatjuk súlyozással is, amikor megengedjük, hogy a pontok multiplicitással (azaz valamilyen pozitív egész súllyal) rendelkezzenek, és azt követeljük meg, hogy minden \(k\) dimenziós altér \(B\)-ből legalább \(t\) összsúlnyi pontot tartalmazzon. Ha vesszük \(t\) darab \((n-k)\) dimenziós altér összegét (súlyozott unióját), akkor persze súlyozott \(t\)-szeres \((n-k)\)-lefogót kapunk. Blázsik Zoltánnal és Szőnyi Tamással azt igazoltuk, hogy ha \(q = p\) prím, \(t \leq 3p/8 + 1\), és \(B\) egy legfeljebb \((t+1/2)q^{n-k} - 1/2\) összsúlyú \(t\)-szeres súlyozott \((n-k)\)-lefogó ponthalmaz, akkor \(B\) szükségképpen tartalmazza \(t\) darab \((n-k)\) dimenziós altér összegét. Ennek az eredménynek a bizonyítását fogom tárgyalni.

The Turán number \(\mathrm{ex}(n, T_k[r])\) of the blow-ups of trees

Mar 22, Zoltán Lóránt Nagy

In this talk we prove the following theorem.

Theorem
Let \(T_k\) denote a tree on \(k\) vertices and \(T_k[r]\) denotes its blow-up, where every vertex is replaced by an independent set of \(r\) vertices. Then \(\mathrm{ex}(n, T_k[r])= Cn^{2-1/r}\) holds with a constant \(C\) depending on \(r\) and \(k\).

To put this result into perspective, we present a short survey on recent (and not so recent) results concerning the maximum number of edges of simple graphs \(G_n\) which do not contain a certain bipartite graph \(F\); where we focus on the case when \(F\) is \(r\)-degenerate, i.e., every subgraph of \(F\) has a vertex of degree at most \(r\). An old conjecture of Erdős asserts that the order of magnitude is at most \(n^{2-1/r}\). This has been proved for some classes of \(r\)-degenerate graphs by Zoltán Füredi, and later Alon, Krivelevich and Sudakov showed that a weaker upper bound of \(O(n^{2-1/(4r)})\) holds, by applying the so-called Dependent Random Choice technique. We point out the connection between our new result and the previously known ones, and also prove a generalization.
Joint work with Andrzej Grzesik (Jagellonian University)