Zbalansowane podziały grafów bez K_4.

Odległością od zbalansowanego grafu dwudzielnego nazywamy ilość krawędzi, którą trzeba usunąć z grafu, aby stał się on zbalansowany dwudzielny.Jedną z motywacji badania tego parametru grafowego jest jego powiązanie ze słynną hipotezą Erdősa o rzadkiej połówce, która mówi, że każdy graf bez trójkątów na n wierzchołkach posiada zbiór n/2 wierzchołków, w którym jest co najwyżej n^2/50 krawędzi.W klasie grafów bez trójkątów udowodniono ciasne ograniczenie górne na odległość od zbalansowanego grafu dwudzielnego, które wynosi n^2/16.W klasie grafów bez K_4, problem znalezienia analogicznego ograniczenia górnego jest nierozwiązany.Wiemy, że to ograniczenie na pewno nie będzie lepsze niż n^2/9, ponieważ dla pełnego zbalansowanego grafu trójdzielnego wartość tego parametru wynosi dokładnie tyle.Najlepszy znany wynik ogranicza ten parametr z góry przez n^2/9 dla trójdzielnych grafów bez K_4.W naszej pracy, ściśle poprawiamy ten wynik dowodząc tego ograniczenia dla kilku nietrywialnych klas grafów bez K_4. Naszą najważniejszą kontrybucją jest udowodnienie tej hipotezy dla grafów o minimalnym stopniu wynoszącym przynajmniej n/2.Istota tego wyniku wynika z faktu, że dla pełnego zbalansowanego grafu trójdzielnego na n wierzchołkach zachodzi δ(G) ⩾ 2n/3, czyli uzyskany rezultat jest ostrym otoczeniem grafu ekstremalnego.Nasz dowód opiera się m.in na algebrach flagowych i jest wspierany komputerowo. Przedstawiamy kilka sposobów na osłabienie wymogu na minimalny stopień do n(1/2 - ε) dla małego, dodatniego ε.

By balanced bipartite distance of a graph we denote the number of edges that need to be removed to make it balanced bipartite.The main motivation for researching this graph parmeter is its connection to the famous sparse half conjecture of Erdős, which states that every triangle-free graph on n vertices has a subset of n/2 vertices that spans at most n^2/50 edges.In the class of triangle-free graphs, a tight upper bound of n^2/16 on the balanced bipartite distance has been proven.In the class of K_4-free graphs, the problem of proving analogous upper bound is unsolved.We know that it cannot be better than n^2/9, as complete balanced tripartite graph attains this exact value of this parameter.The best known result proves the upper bound of n^2/9 for tripartite, K_4-free graphs.In this paper, we strictly improve this result by proving the conjecture for multiple, non-trivial classes of K_4-free graphs.Our most notable contribution consists of proving the conjecture for graphs with the minimum degree of at least n/2.The importance of this result stems from the fact that for the complete balanced tripartite graph it holds δ(G) ⩾ 2n/3, so the requirement holds non-tigthly for the extremal example.Our proof relies, among others, on flag algebras, and is computer-assisted. We include a couple of arguments which allow relaxing the requirement on the minimum degree to n(1/2 - ε) for a small, positive ε.