Maximum cuts of graphs with forbidden cycles

angleški

2018

letnik 15, številka 1

grafi   maksimalni prerez   particija

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Za graf ?$G$?, naj ?$f(G)$? označuje maksimalno število povezav v dvodelnem podgrafu grafa ?$G$?. Za celo število ?$m \ge 1$? in za množico ?$\mathcal{H}$? grafov, naj ?$f(m, \mathcal{H})$? označuje minimalno možno kardinalnost ?$f(G)$?, ko ?$G$? preteče vse grafe z ?$m$? povezavami, ki ne vsebujejo nobenega člana množice ?$\mathcal{H}$? kot podgrafa. Še posebej, za dani graf ?$H$?, enostavno pišemo ?$f(m, H)$?, za ?$f(m, \mathcal{H})$?, ko je ?$\mathcal{H} = \{H\}$?. Naj bo ?$r > 4$? fiksno sodo celo število. Alon in drugi (2003) so postavili domnevo, da obstaja pozitivna konstanta ?$c(r)$?, za katero je ?$f(m, C_{r-1}) \ge m/2 + c(r)m^{r/(r+1)}$? za vse ?$m$?. V tem članku pokažemo, da je ?$f(m, C_{r-1}) \ge m/2 + c(r)(m^r \log^4 m)^{1/(r+2)}$? za neko pozitivno konstanto ?$c(r)$? in za vse ?$m$?. Za poljubno določeno celo število ?$s \ge 2$? študiramo tudi funkcijo ?$f(m, \mathcal{H})$? za ?$\mathcal{H} = \{K_{2,s}, C_5\}$? in ?$\mathcal{H} = \{C_4, C_5,\dots , C_{r-1}\}$?, kar oboje izboljšuje rezultat Alona in drugih.

29.05.2020