\documentclass[a4paper,5pt]{article}
\usepackage{varwidth}
\usepackage[slovene]{babel}
\usepackage{amsfonts,amssymb,amsmath}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{graphicx}
\usepackage{fancyvrb}
\usepackage{listings}
\usepackage{hyperref}
\usepackage{amsthm}
\usepackage[nottoc]{tocbibind}
\usepackage{biblatex}
\usepackage{authblk}
\usepackage{fullpage}
\addbibresource{Prispevek.bib}

\def\N{\mathbb{N}} % mnozica naravnih stevil
\def\Z{\mathbb{Z}} % mnozica celih stevil
\def\Q{\mathbb{Q}} % mnozica racionalnih stevil
\def\R{\mathbb{R}} % mnozica realnih stevil
\def\C{\mathbb{C}} % mnozica kompleksnih stevil
\newcommand{\geslo}[2]{\noindent\textbf{#1} \quad \hangindent=1cm #2\\[-1pc]}

\def\qed{$\hfill\Box$\newline}   % konec dokaza
\def\qedm{\qquad\Box}   % konec dokaza v matematičnem načinu

\providecommand{\keywords}[1]
{
  \small	
  \textbf{\textit{Ključne besede---}} #1
}

\begin{document}
\newtheorem{izrek}{Izrek}[section]
\newtheorem{trditev}[izrek]{Trditev}
\newtheorem{posledica}[izrek]{Posledica}
\newtheorem{lema}[izrek]{Lema}
\newtheorem{opomba}[izrek]{Opomba}
\newtheorem{definicija}[izrek]{Definicija}
\newtheorem{zgled}[izrek]{Zgled}

\title{Eksplicitna geometrijska konstrukcija Ramseyevih grafov brez trikotnikov}

\author[1]{Matija Kocbek\thanks{Fakulteta za matematiko in fiziko, Univerza v Ljubljani, Slovenija. e-naslov: mkocbek1@gmail.com}}
\maketitle

\begin{abstract}
Opišemo eksplicitno geometrijsko konstrukcijo velike družine grafov brez $k$-klik z omejenim neodvisnostnim številom, ki posplošijo Ramseyeve grafe brez trikotnikov, ki so jih opisali Codenotti, Pudlák in Resta, ter podamo nov kombinatorični dokaz za zgornjo mejo neodvisnostnega števila slednjih. 
Osredotočimo se na grafe brez trikotnikov in predstavimo nekaj družin takšnih grafov na $n$ vozliščih z neodvisnostnim številom reda $O(n^{\frac{2}{3}})$, ki nam dajo konstruktivno asimptotsko spodnjo mejo $\Omega(t^{\frac{3}{2}})$ za Ramseyeva števila $R(3, t)$, kar doseže najboljšo znano konstruktivno spodnjo mejo. 
Opišemo še dodatno družino grafov, ki nam ne dajo najboljše znane meje, vendar imajo še vedno polinomsko neodvisnostno število glede na število vozlišč in so zasnovani na evklidski geometriji. Določimo tudi potreben pogoj na parametre, za katere bi lahko ta družina grafov porodila boljše konstruktivne asimptotske 
spodnje meje za $R(s, t)$, kot so trenutno znane, pri čemer se zopet osredotočimo na $R(3, t)$. Predstavimo tudi linearen aproksimacijski algoritem za iskanje največje neodvisne množice v tej parametrizirani družini grafov, ki je $\frac{1}{2}$-aproksimacijski za njeno pomembno poddružino.
\end{abstract}

\keywords{Ramseyeva števila, grafi brez trikotnikov, načrti, diskretna geometrija}

\section{Uvod}

Podgraf nekega grafa je klika, če sta poljubni dve vozlišči v tem podgrafu sosednji. Podgraf nekega grafa je neodvisna množica, če nobeni dve vozlišči v tem podgrafu nista sosednji. Ramseyev izrek \cite{Ramsey1930} v posebnem primeru pravi:

    \begin{izrek}
        Za vsaki naravni števili $s, t \geq 3$ obstaja naravno število $n$, da bo vsak graf z vsaj $n$ vozlišči vseboval kliko velikosti $s$ ali neodvisno množico velikosti $t$. Najmanjšemu takšnemu $n$ pravimo Ramseyevo število $R(s, t)$.
    \end{izrek}

Natančno določanje Ramseyevih števil je izredno težka naloga, zato se dosti ukvarjamo z določanjem asimptotskega obnašanja teh števil. Edina Ramseyeva števila, katerih natančno asimptotiko poznamo, so števila $R(3, t)$. Leta 1980 so Ajtai, Koml{\'o}s in Szemer{\'e}di \cite{Ajtai1980} dokazali asimptotsko zgornjo mejo za Ramseyevo število $R(3, t)$, leta 1995 pa je Kim \cite{Kim95} nekonstruktivno pokazal, da je ta zgornja meja asimptotsko tesna:

    \begin{izrek}
        $R(3, t) = \Theta\left(\frac{t^2}{\log{t}}\right).$
    \end{izrek}

Veliko zanimanja pa je tudi za poskuse konstruktivnih dokazov spodnje asimptotske meje za $R(3, t)$. Do današnjega dne je najboljša konstruktivna spodnja meja podana z $R(3, t) = \Omega(t^{\frac{3}{2}})$. Prvi članek, ki je predstavil eksplicitno konstrukcijo družine grafov brez trikotnikov z $n$ vozlišči in neodvisnostnim številom reda $O(n^{\frac{2}{3}})$ je bil \cite{Alon94}. Kasneje so novo konstrukcijo takšnih grafov predstavili v 
\cite{CodenottiPR00}. 

Kostochka, Pudlák in Rödl \cite{Kostochka2010} so leta 2010 prvi predstavili posplošitev grafov iz \cite{CodenottiPR00}. Osredotočili so se na nekaj specifičnih grafov brez klik velikosti $4$, $5$ oz. $6$, ki so jih definirali podobno kot grafe brez trikotnikov iz \cite{CodenottiPR00}, in s pomočjo le-teh prišli do novih najboljših konstruktivnih spodnjih asimptotskih mej za $R(4, t), R(5, t)$ in $R(6, t)$, ki še do danes niso bile izboljšane. Prav tako so prvi predstavili 
kombinatoričen dokaz za zgornjo mejo neodvisnostnega števila teh grafov, saj je v \cite{CodenottiPR00} bil predstavljen le algebraičen dokaz.

V tem članku bomo predstavili drugačno posplošitev teh grafov in s pomočjo le-te tudi nov kombinatoričen dokaz zgornje meje za njihovo neodvisnostno število. Najprej bomo definirali incidenčno strukturo, ki posploši pojme $t$-terno uravnoteženih načrtov in pakiranj, ki do zdaj še ni bila opisana, kolikor nam je znano. Predstavili bomo neenakost, ki povezuje število točk, blokov in incidenčnih parov v tej strukturi. Na podlagi te incidenčne relacije bomo definirali veliko 
parametrizirano družino grafov brez $k$-klik in s pomočjo prej omenjene neenakosti določili potreben pogoj na parametre, za katere bi lahko dobili grafe, ki bi nam dali nove in boljše konstruktivne asimptotske spodnje meje za Ramseyeva števila $R(s, t)$ za poljuben $s, t \geq 3$, pri čemer se bomo osredotočili na $R(3, t)$.
Prav tako bo ta družina grafov porodila dosti do zdaj še neopisanih primerov grafov brez trikotnikov z neodvisnostnim številom, ki ima polinomski red glede na število vozlišč. Nekaj jih bomo tudi eksplicitno navedli, med drugim tudi dve novi konstrukciji družin grafov brez trikotnikov na $n$ vozliščih z neodvisnostnim številom reda $O(n^{\frac{2}{3}})$. 
Ena izmed teh dveh družin bo prva eksplicitna konstrukcija družine grafov brez trikotnikov na $n$ vozliščih s takšnim neodvisnostnim številom, ki obstaja za poljuben $n$, saj sta tako \cite{Alon94} kot tudi \cite{CodenottiPR00} predstavila konstrukcije le za $n$ posebne oblike. Vsi rezultati, ki so v tem članku povzeti iz literature, so kot takšni navedeni. Rezultati brez referenc so originalni.

\section{Geometrijska konstrukcija grafov brez $k$-klik z omejenim neodvisnostnim številom}

Definirajmo najprej centralni objekt, s katerim bomo delali.

    \begin{definicija}
        Naj bodo $m, \lambda \in \mathbb{N}$, $\mathcal{A}$ množica, katere elemente imenujemo točke, in $\mathcal{B} \subseteq \mathcal{P}(A)$ množica podmnožic $A$ (elementom $\mathcal{B}$ pravimo bloki), za katere velja:
            \begin{enumerate}
                \item Poljubnih $m$ različnih točk je skupaj vsebovano v kvečjemu $\lambda$ blokih.
                \item Vsaka točka je vsebovana v vsaj enem bloku.
                \item Vsak blok je neprazen.
            \end{enumerate}
        Potem pravimo, da je $\mathcal{B}$ \emph{šibko $m$-terno uravnotežen načrt} nad $\mathcal{A}$ s parametrom $\lambda$.
    \end{definicija}

    \begin{definicija}
        Naj bo $x \in \mathcal{A}$ in $B \in \mathcal{B}$. Če je $x \in B$, pravimo, da je $(x, B)$ incidenčni par.
    \end{definicija}

    \begin{definicija}
        Naj bosta $m, \lambda \in \mathbb{N}$ in $\mathcal{B}$ šibko $m$-terno uravnotežen načrt nad neko množico $\mathcal{A}$ s parametrom $\lambda$. Naj bo $<$ poljubna stroga linearna urejenost množice $\mathcal{A}$. Definiramo graf $\Gamma_{\mathcal{B}}^{m, \lambda}$ tako, 
        da za vozlišča vzamemo vse incidenčne pare in dve vozlišči $(x, B_1)$ in $(y, B_2)$ imata med seboj povezavo, če velja $x < y$, $B_1$ in $B_2$ sta različna ter $x \in B_2$.
    \end{definicija}

Opazimo, da notacija zanemarja dejstvo, da je tako definirani graf odvisen tudi od množice $\mathcal{A}$ in linearne urejenosti $<$. Tako postopamo zaradi enostavnosti pisanja, vendar ohranimo to dejstvo v mislih. Raziščimo lastnosti teh grafov:

    \begin{trditev}
        Naj bo $\mathcal{B}$ šibko $m$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda$. Potem $\Gamma_{\mathcal{B}}^{m, \lambda}$ ne vsebuje klike velikosti $m + \lambda$.
    \end{trditev}

    \begin{proof}
        Dokazujemo s protislovjem. Denimo, da imamo kliko $(x_1, B_1), (x_2, B_2), \ldots, (x_{m + \lambda}, B_{m + \lambda})$. Potem so vse točke paroma različne in vsi bloki paroma različni. Brez škode za splošnost denimo, da je $x_1 < x_2 < \ldots < x_{m + \lambda}$. Potem po konstrukciji velja
        $x_1, \ldots, x_{m} \in B_{m + i}$ za vse $i \in \{0, \ldots, \lambda\}$. Ker je $m$ različnih točk v $\mathcal{B}$ vsebovano v kvečjemu $\lambda$ različnih blokov, je to protislovje, in zato $\Gamma_{\mathcal{B}}^{m, \lambda}$ res ne vsebuje klike velikosti $m + \lambda$.
    \end{proof}

V tem članku standardno označimo velikost največje neodvisne množice v grafu $G$ z $\alpha(G)$.

    \begin{trditev}
        Naj bo $\mathcal{B}$ šibko $m$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda$. Potem je $\alpha(\Gamma_{\mathcal{B}}^{m, \lambda}) \leq |\mathcal{A}| + |\mathcal{B}|$.
    \end{trditev}

    \begin{proof}
        Naj bo $H \subseteq V(\Gamma_{\mathcal{B}}^{m, \lambda})$ poljubna neodvisna množica vozlišč. Potem lahko $H$ zapišemo kot disjunktno unijo dveh množic.

        Prva množica $H_1$ vsebuje vse incidenčne pare iz $H$, za katere se točka pojavi v vsaj dveh različnih incidenčnih parih iz $H$. Vzemimo dva takšna incidenčna para, ki delita isto točko, recimo $(x, B_1)$ in $(x, B_2)$.
        Ker je $H$ neodvisna, za vsak $(y, B_2) \in H, y \neq x$, mora veljati $y < x$, saj bi drugače imeli povezavo med $(x, B_1)$ in $(y, B_2)$, kar bi bilo v protislovju z neodvisnostjo $H$. Podobno 
        za vsak $(y, B_1) \in H, y \neq x$, mora veljati $y < x$, saj bi sicer imeli povezavo med $(x, B_2)$ in $(y, B_1)$. To pomeni, da je med vsemi točkami, ki se pojavijo v $H$ v paru z $B_1$, $x$ maksimalna.
        Sledi, da je za vsak $(z, B) \in H_1$, $z$ maksimalen med vsemi točkami, ki se pojavijo v paru z $B$ v $H$, torej se vsak blok $B$ lahko pojavi v $H_1$ v paru s kvečjemu eno točko. Torej je $|H_1| \leq |\mathcal{B}|$.

        Druga množica $H_2$ vsebuje vse incidenčne pare, za katere se točka pojavi v natanko enem paru iz $H$. Očitno je potem $|H_2| \leq |\mathcal{A}|$.
        
        Ker je $H = H_1 \cup H_2$, velja $|H| \leq |\mathcal{A}| + |\mathcal{B}|$ in zato $\alpha(\Gamma_{\mathcal{B}}^{m, \lambda}) \leq |\mathcal{A}| + |\mathcal{B}|$.
    \end{proof}

    \begin{trditev}
        Naj bo $\mathcal{B}$ šibko $m$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda$. Potem je $|\mathcal{B}| \leq \alpha(\Gamma_{\mathcal{B}}^{m, \lambda})$.
    \end{trditev}

    \begin{proof}
        Pokazali bomo, da vsak graf $\Gamma_{\mathcal{B}}^{m, \lambda}$ vsebuje neodvisno množico velikosti $|\mathcal{B}|$. Pokazali bomo z indukcijo na $n = |\mathcal{B}|$.

        Za $n = 0$ je trditev očitna in baza indukcije izpolnjena. Naj bo $n \geq 1$ in denimo, da je trditev resnična za vsa manjša naravna števila. Naj bo $\mathcal{B}$ moči $n$ šibko $m$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda$. Naj bo $x$ najmanjša točka v $\mathcal{A}$ in naj bo $\mathcal{C}$ množica vseh blokov, ki vsebujejo $x$. Naj bo $\mathcal{I}_1$ množica vseh incidenčnih parov, ki vsebujejo $x$ in bloke iz $\mathcal{C}$.
        Ta množica je očitno neodvisna, saj imajo vsi incidenčni pari v njej isto točko. Naj bo nadalje $\mathcal{D} = \mathcal{B} \setminus \mathcal{C}$. Potem po konstrukciji množice $\mathcal{C}$, $x$ ni vsebovan v nobenem izmed blokov iz $\mathcal{D}$. Naj bosta $y \in \mathcal{A} \setminus \{p\}$ in $B_2 \in \mathcal{D}$ takšna, da je $y \in B_2$, in naj bo $(x, B_1) \in \mathcal{I}_1$. 
        Zaradi minimalnosti $x$, sta incidenčna para $(x, B_1)$ in $(y, B_2)$ lahko sosednja samo, če je $x \in B_2$, kar je nemogoče, ker $x$ ni vsebovan v nobenem bloku iz $\mathcal{D}$. Torej $\mathcal{I}_1$ ne deli povezave z nobenim incidenčnim parom s točko iz $\mathcal{A}$ in blokom iz $\mathcal{D}$ ter je drugačen od vsakega takšnega para. Naj bo $A' \subseteq A$ 
        množica točk iz $A$, ki so vsebovane v kakšnem bloku iz $\mathcal{D}$. Tedaj je $\mathcal{D}$ šibko $m$-terno uravnotežen načrt nad $\mathcal{A}'$ s parametrom $\lambda$ in $\Gamma_{\mathcal{D}}^{m, \lambda}$ je izomorfen podgrafu $H$ grafa $\Gamma_{\mathcal{B}}^{m, \lambda}$, ki je vpet na vozliščih s točkami iz $A'$ in bloki iz $D$. Dokazali smo že, da je ta podgraf neodvisen in disjunkten z $\mathcal{I}_1$. 
        Ker je $x$ vsebovan v vsaj enem bloku, je $C$ neprazna množica in zato $|D| < n$. Potem ima po indukcijski predpostavki $\Gamma_{\mathcal{D}}^{m, \lambda}$, in s tem tudi $H$, neodvisno množico $\mathcal{I}_2$ moči $|\mathcal{D}|$. Tedaj je $\mathcal{I} = \mathcal{I}_1 \cup \mathcal{I}_2$ neodvisna množica v $\Gamma_{\mathcal{B}}^{m, \lambda}$ moči $|\mathcal{C}| + |\mathcal{D}| = |\mathcal{B}|$, kar zaključi dokaz.
    \end{proof}

Dokaz zgornje trditve nam da algoritem, s katerim lahko učinkovito najdemo neodvisno množico moči $|\mathcal{B}|$ v $\Gamma_{\mathcal{B}}^{m, \lambda}$. Začnemo s prazno neodvisno množico. Vzamemo najmanjšo točko in dodamo v neodvisno množico vse incidenčne pare, v katerih ta točka nastopa. Iz množice vseh točk in blokov odstranimo to točko in vse bloke, ki jo vsebujejo. Ponovno vzamemo najmanjšo 
izmed preostalih točk in v neodvisno množico dodamo vse incidenčne pare, v katerih nastopa ta točka z neodstranjenimi bloki. Nadaljujemo ta postopek, dokler nam ne zmanjka blokov. Če primerno shranimo incidence, ima ta algoritem časovno zahtevnost $O(|\mathcal{A}| + |\mathcal{B}|)$. 

Prejšnja trditev nam prav tako da naslednjo očitno posledico, ki nam v posebnem primeru pove, da je neodvisnostno število premo sorazmerno s številom točk in blokov, če imamo več blokov kot točk.

    \begin{posledica}
        Naj bo $\mathcal{B}$ šibko $m$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda$. Denimo, da je $|\mathcal{A}|^{\varepsilon} \leq k|\mathcal{B}|$ za nek $k > 0$ in nek $0 < \varepsilon \leq 1$. Potem velja $\frac{|\mathcal{A}|^{\varepsilon} + |\mathcal{B}|}{k + 1} \leq \alpha(\Gamma_{\mathcal{B}}^{m, \lambda})$.
    \end{posledica}

Za veliko pomembnih razredov šibko $m$-terno uravnoteženih načrtov je znano, da je $|\mathcal{A}| \leq |\mathcal{B}|$, kot na primer za \emph{$t$-načrte} ali \emph{parno uravnotežene načrte} pri določenih pogojih, ki zagotavljajo netrivialnost. 
    
Šibko $m$-terno uravnotežen načrt $\mathcal{B}$ nad $\mathcal{A}$ s parametrom $\lambda$ je $m$-načrt s parametri $(v, k, \lambda)$, če je $|\mathcal{A}| = v$, če vsak blok vsebuje natanko $k$ točk in če je poljubnih $m$ paroma različnih točk vsebovano skupaj v natanko $\lambda$ blokov. Fisherjeva neenakost \cite{Fisher40} nam pove, da za takšen $m$-načrt $\mathcal{B}$, ob dodatnem pogoju, da je $k < v$, velja $|\mathcal{A}| \leq |\mathcal{B}|$. To nam pove naslednje:

    \begin{posledica}
        Naj bo $\mathcal{B}$ $m$-načrt s parametri $(v, k, \lambda)$ nad $\mathcal{A}$ in naj bo $k < v$. Potem je $\frac{|\mathcal{A}| + |\mathcal{B}|}{2} \leq \alpha(\Gamma_{\mathcal{B}}^{m, \lambda}) \leq |\mathcal{A}| + |\mathcal{B}|$. 
    \end{posledica}

Podobno pravimo za šibko $2$-terno uravnotežen načrt $\mathcal{B}$ s parametrom $\lambda$, da je parno uravnotežen načrt s parametrom $\lambda$, če vsak blok vsebuje vsaj dve točki in če sta poljubni dve točki skupaj vsebovani v natanko $\lambda$ blokov. Erd\H{o}s-de Bruijnov izrek \cite{Bruijn48} nam pove, da za $\mathcal{B}$, ki je parno uravnotežen načrt s parametrom $\lambda = 1$ in v katerem noben blok ne vsebuje celega $\mathcal{A}$, velja $|\mathcal{A}| \leq |\mathcal{B}|$.
Velja pa tudi njegova posplošitev za poljuben $\lambda$.\cite{Stinson2004} Od tod sledi:

    \begin{posledica}
        Naj bo $\mathcal{B}$ parno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda$, v katerem noben blok ne vsebuje celega $\mathcal{A}$. Potem velja $\frac{|\mathcal{A}| + |\mathcal{B}|}{2} \leq \alpha(\Gamma_{\mathcal{B}}^{2, \lambda}) \leq |\mathcal{A}| + |\mathcal{B}|$.
    \end{posledica}

V teh primerih, ko je $|\mathcal{A}| \leq |\mathcal{B}|$, je prej opisani algoritem $\frac{1}{2}$-aproksimacijski, torej nam vedno vrne neodvisno množico, ki je kvečjemu dvakrat manjša od največje neodvisne množice.

Imamo tudi drugačno spodnjo mejo za neodvisnostno število grafa $\Gamma_{\mathcal{B}}^{m, \lambda}$, ki je uporabna, ko imamo več točk kot blokov:

    \begin{trditev}
        Naj bo $\mathcal{B}$ šibko $m$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda$. Potem je $\frac{|\mathcal{A}|}{|\mathcal{B}|} \leq \alpha(\Gamma_{\mathcal{B}}^{m, \lambda})$.
    \end{trditev}

    \begin{proof}
        Dokazali bomo, da $\Gamma_{\mathcal{B}}^{m, \lambda}$ vsebuje neodvisno množico moči vsaj $\frac{|\mathcal{A}|}{|\mathcal{B}|}$. Pokažimo, da nek blok mora vsebovati vsaj $\frac{|\mathcal{A}|}{|\mathcal{B}|}$ točk. Denimo nasprotno. Ker je vsaka točka vsebovana v nekem bloku, velja $\bigcup_{B \in \mathcal{B}}B = A$. Po drugi strani pa velja tudi $|\bigcup_{B \in \mathcal{B}}B| < |\mathcal{B}|\frac{|\mathcal{A}|}{|\mathcal{B}|} = |\mathcal{A}|$,
        kar je protislovje. Obstaja torej blok $B$, ki vsebuje vsaj $\frac{|\mathcal{A}|}{|\mathcal{B}|}$ točk. Tedaj je množica $\mathcal{I} = \{(x, B); x \in B\}$ neodvisna in ima moč vsaj $\frac{|\mathcal{A}|}{|\mathcal{B}|}$, kar dokaže trditev.
    \end{proof}
\vspace{-2ex}
Ta spodnja meja nam skupaj s prejšnjo, da naslednjo posledico:

    \begin{posledica}
        Naj bo $\mathcal{B}$ šibko $m$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda$. Denimo, da je $|\mathcal{B}| \leq k|\mathcal{A}|^{1-\varepsilon}$ za neka $k > 0$ in $0 < \varepsilon < 1$. Tedaj je $\frac{k|\mathcal{A}|^{\varepsilon} + |\mathcal{B}|}{2} \leq \alpha(\Gamma_{\mathcal{B}}^{m, \lambda})$.
    \end{posledica}

\section{Geometrijska konstrukcija grafov brez trikotnikov s polinomskim neodvisnostnim številom}

Osredotočimo se na primer, ko grafi $\Gamma_{\mathcal{B}}^{m, \lambda}$ ne vsebujejo trikotnikov. V primeru, ko je $m = 1$ in $\lambda = 2$, je $|\mathcal{A}| \geq \frac{n}{2}$, kjer je $n$ število incidenčnih parov oziroma vozlišč v grafu $\Gamma_{\mathcal{B}}^{m, \lambda}$. 
Zato nam zgornja meja za neodvisnostno število iz prejšnjega razdelka ne porodi nobene asimptotsko netrivialne meje. Poglejmo zato primer, ko je $m = 2$ in $\lambda = 1$ ter označimo pripadajoči graf preprosto kot $\Gamma_{\mathcal{B}}$. Naslednja trditev nam da dve neenakosti, ki povezujeta število točk, blokov in incidenčnih parov v šibko $2$-terno uravnoteženem načrtu s parametrom $\lambda = 1$:

    \begin{trditev} (Ravsky, Stack Exchange)
        Naj bo $\mathcal{B}$ šibko $2$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda = 1$. Naj bo $n$ število incidenčnih parov. Označimo $a = |\mathcal{A}|$ in $b = |\mathcal{B}|$. Tedaj velja:
        \begin{align*}
            a &\geq \frac{n^2}{b^2 - b + n}\\
            b &\geq \frac{n^2}{a^2 - a + n}.
        \end{align*}
    \end{trditev}

    \begin{proof}
        Naj bo $a = |\mathcal{A}|$ in $b = |\mathcal{B}|$. Opazujmo tabelo $A \times B$, v kateri pobarvamo celico $(x, B)$, če je $x \in B$. Ker se dve točki skupaj nahajata v kvečjemu enem bloku, celice $(x, B_1), (y, B_1), (x, B_2)$ in $(y, B_2)$ ne morejo biti vse pobarvane za katerekoli različne $x, y \in \mathcal{A}$ in različne $B_1, B_2 \in \mathcal{B}$. Pravimo, da tabela ne vsebuje pravokotnikov poravnanih z osmi.

        Pokažimo bolj splošno neenakost za tabele brez pravokotnikov poravnanih z osmi. Imejmo tabelo z $a$ vrsticami in $b$ stolpci. Označimo njene elemente z $m_{ij}$. Potem ne obstajajo indeksi $i, j, k \text{ in } l$, da so $t_{ik}, t_{il}, t_{jk}$ in $t_{jl}$ vsi pobarvane celice. Pravimo, da vrstica $i$
        prepove par stolpcev $\{j, k\}$, če sta tako $m_{ij}$ kot $m_{ik}$ pobarvana. Kot smo prej pokazali, nobeni dve vrstici ne moreta prepovedati istega para stolpcev. Označimo z $l_i$ število pobarvanih celic v $i$-ti vrstici. Tedaj vrstica $i$
        prepove natanko $\binom{l_i}{2}$ parov stolpcev. Ker nobeni vrstici ne moreta prepovedati istega para stolpcev in ker je skupaj $\binom{b}{2}$ parov stolpcev, velja $\sum_{i=1}^a\binom{l_i}{2} \leq \binom{b}{2}$ oz. $b^2 - b \geq \sum_{i=1}^{a}l_i^2 - \sum_{i=1}^{a}l_i$. Po Cauchy-Schwarzovi neenakosti tedaj dobimo 
        $$b^2 - b \geq \frac{1}{a}\left(\sum_{i=1}^{a}l_i\right)^2 - \sum_{i=1}^{a}l_i.$$

        Če se vrnemo v naš kontekst, vemo, da velja $n = \sum_{i=1}^{a}l_i$ in zato $n^2 - an - a(b^2 - b) \leq 0$. Če to rešimo kot kvadratično neenakost dobimo 
        $$a \geq \frac{n^2}{b^2 - b + n}.$$
        Če bi ponovili isti dokaz, vendar bi opazovali stolpce, ki prepovedujejo pare vrstic namesto obratno, bi dobili
        $$b \geq \frac{n^2}{a^2 - a + n}.$$
    \end{proof}
\vspace{-3ex}
Ti neenakosti nam dasta asimptotske spodnje meje za število točk in blokov v šibko $2$-terno uravnoteženem načrtu s parametrom $\lambda = 1$:

    \begin{posledica}
        Naj bo $\mathcal{B}$ šibko $2$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda = 1$. Naj bo $\varepsilon > 0$ in $\varepsilon \leq 1$. Če je $\varepsilon > \frac{1}{2}$, potem je $|\mathcal{A}|^{\varepsilon} + |\mathcal{B}| = \Omega(n^{\frac{2\varepsilon}{2\varepsilon + 1}})$. Sicer je $|\mathcal{A}|^{\varepsilon} + |\mathcal{B}| = \Omega(n^{\varepsilon})$.
    \end{posledica}

    \begin{proof}
        Najprej dokažimo primer, ko je $\varepsilon > \frac{1}{2}$. Če je $|\mathcal{B}| = \Omega(n^{\frac{2\varepsilon}{2\varepsilon + 1}})$, je trditev očitna. Sicer je $|\mathcal{B}| = o(n^{\frac{2\varepsilon}{2\varepsilon + 1}})$ in je zato po prvi neenakosti iz prejšnje trditve $|\mathcal{A}|^{\varepsilon} = \Omega(n^{\frac{2\varepsilon}{2\varepsilon + 1}})$, kar dokaže to trditev.
        Dokažimo zdaj še primer, ko je $\varepsilon \leq \frac{1}{2}$. Če je $|\mathcal{B}| = \Omega(n^{\frac{1}{2}})$, je trditev resnična, ker je $\varepsilon \leq \frac{1}{2}$. Sicer je $|\mathcal{B}| = o(n^{\frac{1}{2}})$ in je zato po prvi neenakosti iz prejšnje trditve $|\mathcal{A}|^{\varepsilon} = \Omega(n^{\varepsilon})$, kar dokaže to trditev.
    \end{proof}
\vspace{-2ex}
To skupaj s spodnjimi mejami iz prejšnjega razdelka dokaže netrivialne asimptotske spodnje meje za neodvisnostno število velikih poddružin grafov $\Gamma_{\mathcal{B}}$. Prva spodnja meja velja, ko je v $\mathcal{B}$ nad $\mathcal{A}$ število točk asimptotsko strogo manjše od kvadrata števila blokov.

    \begin{posledica}
        Naj bo $\mathcal{B}$ šibko $2$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda = 1$. Naj bo $|\mathcal{A}|^{\varepsilon} \leq k|\mathcal{B}|$ za nek $k > 0$ in nek $\frac{1}{2} < \varepsilon \leq 1$, tj. $|\mathcal{A}|^{\varepsilon} = O(|\mathcal{B}|)$. Naj bo $n$ število incidenčnih parov, tj. število vozlišč v $\Gamma_{\mathcal{B}}$. Potem je $\alpha(\Gamma_{\mathcal{B}}) = \Omega(n^{\frac{2\varepsilon}{2\varepsilon + 1}})$.
    \end{posledica}

Druga spodnja meja velja, ko je v $\mathcal{B}$ nad $\mathcal{A}$ število točk asimptotsko strogo večje od kvadrata števila blokov:

    \begin{posledica}
        Naj bo $\mathcal{B}$ šibko $2$-terno uravnotežen načrt nad $\mathcal{A}$ s parametrom $\lambda = 1$. Denimo, da je $|\mathcal{B}| \leq k|\mathcal{A}|^{1-\varepsilon}$ za nek $k > 0$ in $\frac{1}{2} < \varepsilon < 1$, tj. $|\mathcal{B}| = O(|\mathcal{A}|^{1-\varepsilon})$. Naj bo $n$ število incidenčnih parov, tj. število vozlišč v $\Gamma_{\mathcal{B}}$. Potem je $\alpha(\Gamma_{\mathcal{B}}) = \Omega(n^{\frac{2\varepsilon}{2\varepsilon + 1}})$.
    \end{posledica}

Prejšnji posledici smo navedli samo za $\varepsilon > \frac{1}{2}$, saj nam za manjše $\varepsilon$ trditve iz tega razdelka dajo samo $\alpha(\Gamma_{\mathcal{B}}) = \Omega(n^{\varepsilon})$. Vendar to ne bi bila nova spodnja meja, saj nam dejstvo, da je $R(3, t) = \Theta\left(\frac{t^2}{\log{t}}\right)$, pove, da je $\alpha(\Gamma_{\mathcal{B}}) = \Omega(\sqrt{n\log{n}})$.

Prejšnje posledice nam povejo, da v primeru, da obstaja šibko $2$-terno uravnotežen načrt s parametrom $\lambda = 1$, za katerega je ta spodnja meja za $\alpha(\Gamma_{\mathcal{B}})$ dosežena, mora zanj veljati $|\mathcal{A}| = \omega(|\mathcal{B}|^{2-\varepsilon})$ in $|\mathcal{A}| = o(|\mathcal{B}|^{2+\varepsilon})$ za vsak $\varepsilon > 0$. Posledice nam prav tako povejo, da je v primeru, ko je $|\mathcal{A}| \leq k|\mathcal{B}|$ za nek $k > 0$, neodvisnostno število 
grafa $\Gamma_{\mathcal{B}}$ na $n$ vozliščih vedno reda $\Omega(n^{\frac{2}{3}})$ za katerokoli izbiro $\mathcal{B}$. Pokažimo, da je ta spodnja meja tesna.

Poglejmo poseben primer tega grafa. Če je $k$ potenca nekega praštevila, konstruiramo $P_k$ tako, da vzamemo končno projektivno ravnino reda $k$, tj. končno projektivno ravnino s $k^2 + k + 1$ točkami. Za vozlišča vzamemo vse incidenčne pare $(p, L)$. Množico točk poljubno linearno uredimo in naredimo povezavo med $(p, L)$ in $(p', L')$, če je $p < p'$, $L \neq L'$ in $p \in L'$. 
Graf $P_k$ je poseben primer grafa $\Gamma_{\mathcal{B}}$, pri katerem $\mathcal{A}$ vsebuje $k^2 + k + 1$ točk, $\mathcal{B}$ vsebuje $k^2 + k + 1$ blokov in vsak blok vsebuje $k + 1$ točk. Poljubni dve točki sta skupaj vsebovani v natanko enem bloku. Rezultati iz prejšnjega podrazdelka nam dajo naslednjo trditev, ki je bila dokazana že v \cite{CodenottiPR00}.

    \begin{trditev}
        $P_k$ ne vsebuje trikotnikov in velja $\alpha(P_k) \leq 2 \cdot (k^2 + k + 1)$.
    \end{trditev}

Ker ima $P_k$ natanko $(k^2 + k + 1)(k + 1)$ vozlišč, velja $\alpha(P_k) = O(n^{\frac{2}{3}})$, kjer je $n = |V(P_k)|$. Ker ima projektivna ravnina enako število točk in premic, smo s tem pokazali, da je prejšnja asimptotska spodnja meja za primere, ko je $|\mathcal{A}| \leq |\mathcal{B}|$, tesna.

Na enak način lahko v primerih, ko je $k$ potenca nekega praštevila, zgradimo graf $A_k$ iz afine geometrije reda $k$, tj. afine geometrije s $k^2$ točkami. Takšna ravnina ima $k^2 + k$ premic in vsaka premica vsebuje $k$ točk. Zato velja naslednja trditev:

    \begin{trditev}
        $A_k$ ne vsebuje trikotnikov in velja $\alpha(A_k) \leq 2 k^2 + k$.
    \end{trditev}

Ker ima $A_k$ natanko $k(k^2 + k)$ vozlišč, velja $\alpha(A_k) = O(n^{\frac{2}{3}})$, kjer je $n = |V(A_k)|$. 

Podali smo dve konstrukciji grafov na $n$ vozliščih z neodvisnostnim številom reda $O(n^{\frac{2}{3}})$, vendar sta obe konstrukciji možni le za določene $n$. Konstruirajmo zdaj graf, ki ima $n$ vozlišč in neodvisnostno število reda $O(n^{\frac{2}{3}})$, kjer je $n$ poljubno naravno število. Z odvajanjem vidimo, da je $f(k) = \frac{(k+1)^3 + (k+1)^2}{k^3+k^2}$ padajoča na $[1,\infty)$ in zato velja
$\frac{(k+1)^3 + (k+1)^2}{k^3+k^2} \leq 6$ za $k \in \mathbb{N}$. Zato obstaja $k$, da je $n \leq k^3 + k^2 \leq 6n$. Po Bertrandovem postulatu \cite{Tchebichef1852} obstaja praštevilo $p$, da je $k \leq p \leq 2k$. Naj bosta $\mathcal{A}$ in $\mathcal{B}$ množici točk in premic v končni afini geometriji reda $p$. Potem je $\sum_{L \in B}|L| = p^3 + p^2 \geq n$. Za vsak $L \in B$ lahko izberemo 
$L' \subseteq L$, da bo $\sum_{L \in B}|L \setminus L'| = n$. Naj bo zdaj $\mathcal{B}' = \{L \setminus L'; L \in \mathcal{B}, L \neq L'\}$ in $\mathcal{A}' \subseteq \mathcal{A}$ množica točk, ki je vsebovana v vsaj kakšnem bloku iz $\mathcal{B}'$. Potem je $\mathcal{B}'$ šibko $2$-terno uravnotežen načrt nad $\mathcal{A}'$ s parametrom $\lambda = 1$ in z $n$ incidenčnimi pari. Definirajmo $G_n = \Gamma_{\mathcal{B'}}$. Potem velja $\alpha(G_n) \leq |\mathcal{A}'| + |\mathcal{B}'| \leq 
|\mathcal{A}| + |\mathcal{B}| = 2p^2 + p \leq 8k^2 + 2k \leq 8 \cdot 6\frac{n}{k}$. Ker je $n \leq k^3 + k^2 \leq 2k^3$, dobimo $\alpha(G_n) \leq 48\sqrt[3]{2}n^{\frac{2}{3}}$, kar dokazuje naslednjo trditev:

    \begin{trditev}
        Za vsak $n \in \mathbb{N}$ ima graf $G_n$ natanko $n$ vozlišč, ne vsebuje trikotnikov in velja $\alpha(G_n) = O(n^{\frac{2}{3}})$.
    \end{trditev}

Potrebno je izpostaviti, da so ocene v prejšnjem odstavku zelo grobe. Za vsak $k \geq 4$ velja $\frac{(k+1)^3 + (k+1)^2}{k^3+k^2} \leq 2$, kar je veliko tesnejša ocena. Ko smo ocenjevali porazdelitev praštevil, smo uporabili le Bertrandov postulat, praštevila pa so veliko bolj gosta. Nadalje, sploh nismo vzeli v obzir, da bi lahko namesto praštevila $p$ vzeli katerokoli potenco nekega praštevila in bi dokaz še vedno veljal. Potence
praštevil pa so še občutno bolj goste. Visoka konstanta v oceni bi lahko bila torej občutno nižja.

Na koncu poglejmo še družino grafov, ki jo lahko dobimo z uporabo šibko $2$-terno uravnoteženih načrtov s parametrom $\lambda = 1$ porojenih s točkami in premicami v evklidski ravnini. Naj bo $N \in \mathbb{N}$, $\mathcal{P} = \{(a, b) \in \mathbb{Z}^2; 1 \leq a \leq N, 1 \leq b \leq 2N^2\}$ in $\mathcal{L} = \{\{(x, mx + b); x \in \mathbb{N}, 1 \leq x \leq N\}; m, b \in \mathbb{N}, 1 \leq m \leq N, 1 \leq b \leq N^2\}$. Potem je $|\mathcal{P}| = 2N^3, |\mathcal{L}| = N^3$ in vsak blok vsebuje $N$ točk.
Tako ima $\Gamma_{\mathcal{L}}$ natanko $N^4$ vozlišč in velja $\alpha(\Gamma_{\mathcal{L}}) = O(n^{\frac{3}{4}})$, kjer je $n$ število vozlišč grafa. Ker vemo, da obstaja neodvisna množica moči $|\mathcal{L}| = n^{\frac{3}{4}}$, prav tako vemo, da je ta zgornja meja tesna. Za poljubno množico točk $\mathcal{A}$ in množico premic $\mathcal{B}$ v evklidski ravnini, za katere je $|\mathcal{A}| \leq k|\mathcal{B}|$ za nek $k > 0$, smo pokazali, da je neodvisnostno število
grafa $\Gamma_{\mathcal{B}}$ asimptotsko enako $|\mathcal{A}| + |\mathcal{B}|$. Po Szemer{\'e}di–Trotterjevem izreku \cite{Szemeredi1983} potlej vemo, da ima za takšne množice točk in premic v evklidski ravnini prejšnja konstrukcija asimptotsko najmanjše možno neodvisnostno število, saj nam izrek pove, da za poljubni množici točk in premic $\mathcal{A}$ in $\mathcal{B}$ v evklidski ravnini z $n$ incidenčnimi pari velja $|\mathcal{A}| + |\mathcal{B}| = \Omega(n^{\frac{3}{4}})$.

\section{Diskusija}

V tem članku smo pokazali, da ima za vsak šibko $2$-terno uravnotežen načrt $\mathcal{B}$ s parametrom $\lambda = 1$, ki vsebuje kvečjemu $k|\mathcal{B}|$ točk za nek $k > 0$, graf $\Gamma_{\mathcal{B}}$ neodvisnostno število reda $\Omega(n^{\frac{2}{3}})$, kjer je $n$ število njegovih vozlišč. Vendar ostaja odprto vprašanje, ali lahko dobimo družino grafov brez trikotnikov z manjšim neodvisnostnim številom, če uporabimo nek šibko $2$-terno uravnotežen načrt s parametrom $\lambda = 1$, ki ima asimptotsko strogo več točk kot blokov. 
Še eno vprašanje, ki je ostalo odprto v tem članku, je, ali lahko dobimo boljše konstruktivne asimptotske spodnje meje za $R(s, t)$, kot so določene v \cite{Kostochka2010} in \cite{Alon2001}, za neko izbiro šibko $m$-terno uravnoteženih načrtov s parametrom $s - m$. Za odgovore na ta vprašanja bi bilo potrebno določiti tesnejšo zgornjo ali spodnjo mejo za neodvisnostno število grafov $\Gamma_{\mathcal{B}}^{m, \lambda}$.
\printbibliography
\end{document}