A reminder: this is today
------------------------------------------------------
On 2024-02-05 10:53, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 8 February, given by Tinaz Ekim. Please find the talk details below.
Best regards, Misha Tyomkyn.
Extremal Triangle-free Graphs Tinaz Ekim Bogazici University February 8, 2024, 12:20 in S6
Abstract In this talk, we will address an extremal problem from two perspectives: structural graph theory and Integer Programming (IP). We will determine the maximum number of edges in a triangle-free graph when its maximum degree is at most d and its matching number is at most m for two given integers d and m. We will derive structural properties of extremal triangle-free graphs, which will allow us i) to provide a formula for this maximum number which is valid in most cases, ii) to develop an IP formulation for constructing extremal graphs, which has surprising links with the classical Knapsack problem. We conjecture that our formula giving the size of extremal triangle-free graphs is also valid for all the open cases and endorse this conjecture by solving the IP formulation for some additional cases
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz