"Balanced partitions of K_4-free graphs."

master
dc.abstract.enBy 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 ε.pl
dc.abstract.plOdległ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 ε.pl
dc.affiliationWydział Matematyki i Informatykipl
dc.areaobszar nauk ścisłychpl
dc.contributor.advisorGrzesik, Andrzej - 104622 pl
dc.contributor.authorBuczek, Ignacy - USOS273502 pl
dc.contributor.departmentbycodeUJK/WMI2pl
dc.contributor.reviewerGrzesik, Andrzej - 104622 pl
dc.contributor.reviewerBosek, Bartłomiej - 114402 pl
dc.date.accessioned2024-07-14T23:30:23Z
dc.date.available2024-07-14T23:30:23Z
dc.date.submitted2024-07-12pl
dc.fieldofstudyinformatyka analitycznapl
dc.identifier.apddiploma-176979-273502pl
dc.identifier.urihttps://ruj.uj.edu.pl/handle/item/378869
dc.languageengpl
dc.subject.engraph theory, combinatorics, sparse half, sparse half conjecture, flag algebras, K_4-free, K_4-free graphs, Erdős conjecture, computer-assisted, semidefinite programming, balanced partition, bipartitionpl
dc.subject.plteoria grafów, kombinatoryka, rzadka połówka, hipoteza o rzadkiej połówce, algebry flagowe, bez K_4, grafy bez K_4, hipoteza Erdős'a, dowód wspomagany komputerowo, programowanie półdefiniowane, zbalansowany podział, bipartycjapl
dc.title"Balanced partitions of K_4-free graphs."pl
dc.title.alternativeZbalansowane podziały grafów bez K_4.pl
dc.typemasterpl
dspace.entity.typePublication
dc.abstract.enpl
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 ε.
dc.abstract.plpl
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 ε.
dc.affiliationpl
Wydział Matematyki i Informatyki
dc.areapl
obszar nauk ścisłych
dc.contributor.advisorpl
Grzesik, Andrzej - 104622
dc.contributor.authorpl
Buczek, Ignacy - USOS273502
dc.contributor.departmentbycodepl
UJK/WMI2
dc.contributor.reviewerpl
Grzesik, Andrzej - 104622
dc.contributor.reviewerpl
Bosek, Bartłomiej - 114402
dc.date.accessioned
2024-07-14T23:30:23Z
dc.date.available
2024-07-14T23:30:23Z
dc.date.submittedpl
2024-07-12
dc.fieldofstudypl
informatyka analityczna
dc.identifier.apdpl
diploma-176979-273502
dc.identifier.uri
https://ruj.uj.edu.pl/handle/item/378869
dc.languagepl
eng
dc.subject.enpl
graph theory, combinatorics, sparse half, sparse half conjecture, flag algebras, K_4-free, K_4-free graphs, Erdős conjecture, computer-assisted, semidefinite programming, balanced partition, bipartition
dc.subject.plpl
teoria grafów, kombinatoryka, rzadka połówka, hipoteza o rzadkiej połówce, algebry flagowe, bez K_4, grafy bez K_4, hipoteza Erdős'a, dowód wspomagany komputerowo, programowanie półdefiniowane, zbalansowany podział, bipartycja
dc.titlepl
"Balanced partitions of K_4-free graphs."
dc.title.alternativepl
Zbalansowane podziały grafów bez K_4.
dc.typepl
master
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
18
Views per month
Views per city
Krakow
6
Hefei
3
Warsaw
2
Council Bluffs
1
Niepołomice
1
Poznan
1
São Paulo
1
Wald
1
Wieliczka
1

No access

No Thumbnail Available
Collections