{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/13533"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/13533","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"COMBINATORIAL OPTIMIZATION APPROACHES TO DISCRETE PROBLEMS","abstract":"<p>As stressed by the Society for Industrial and Applied Mathematics (SIAM): Applied mathematics, in partnership with computational science, is essential in solving many real-world problems. Combinatorial optimization focuses on problems arising from discrete structures such as graphs and polyhedra. This thesis deals with extremal graphs and strings and focuses on two problems: the Erdos' problem on multiplicities of complete subgraphs and the maximum number of distinct squares in a string.<br />The first part of the thesis deals with strengthening the bounds for the minimum proportion of monochromatic t cliques and t cocliques for all 2-colourings of the edges of the complete graph on n vertices. Denote by k_t(G) the number of cliques of order t in a graph G. Let k_t(n) = min{k_t(G)+k_t(\\overline{G})} where \\overline{G} denotes the complement of G of order n. Let c_t(n) = {k_t(n)} / {\\tbinom{n}{t}} and c_t be the limit of c_t(n) for n going to infinity. A 1962 conjecture of Erdos stating that c_t = 2^{1-\\tbinom{t}{2}} was disproved by Thomason in 1989 for all t > 3. Tighter counterexamples have been constructed by Jagger, Stovicek and Thomason in 1996, by Thomason for t < 7 in 1997, and by Franek for t=6 in 2002. We present a computational framework to investigate tighter upper bounds for small t yielding the following improved upper bounds for t=6,7 and 8: c_6 \\leq 0.7445 \\times 2^{1- \\tbinom{6}{2}}, c_7\\leq 0.6869\\times 2^{1- \\tbinom{7}{2}}, and c_8 \\leq 0.7002\\times 2^{1- \\tbinom{8}{2}}. The constructions are based on a large but highly regular variant of Cayley graphs for which the number of cliques and cocliques can be expressed in closed form. Considering the quantity e_t=2^{\\tbinom{t}{2}-1} c_t, the new upper bound of 0.687 for e_7 is the first bound for any e_t smaller than the lower bound of 0.695 for e_4 due to Giraud in 1979.<br />The second part of the thesis deals with extremal periodicities in strings: we consider the problem of the maximum number of distinct squares in a string. The importance of considering as key variables both the length n and the size d of the alphabet is stressed. Let (d,n)-string denote a string of length n with exactly d distinct symbols. We investigate the function \\sigma_d(n) = max {s(x) | x} where s(x) denotes the number of distinct primitively rooted squares in a (d,n)-string x. We discuss a computational framework for computing \\sigma_d(n) based on the notion of density and exploiting the tightness of the available lower bound. The obtained computational results substantiate the hypothesized upper bound of n-d for \\sigma_d(n). The structural similarities with the approach used for investigating the Hirsch bound for the diameter of a polytope of dimension d having n facets is underlined. For example, the role played by (d,2d)-polytope was presented in 1967 by Klee and Walkup who showed the equivalency between the Hirsch conjecture and the d-step conjecture.</p>","abstract_html":"&lt;p&gt;As stressed by the Society for Industrial and Applied Mathematics (SIAM): Applied mathematics, in partnership with computational science, is essential in solving many real-world problems. Combinatorial optimization focuses on problems arising from discrete structures such as graphs and polyhedra. This thesis deals with extremal graphs and strings and focuses on two problems: the Erdos&#x27; problem on multiplicities of complete subgraphs and the maximum number of distinct squares in a string.&lt;br /&gt;The first part of the thesis deals with strengthening the bounds for the minimum proportion of monochromatic t cliques and t cocliques for all 2-colourings of the edges of the complete graph on n vertices. Denote by k_t(G) the number of cliques of order t in a graph G. Let k_t(n) = min{k_t(G)+k_t(\\overline{G})} where \\overline{G} denotes the complement of G of order n. Let c_t(n) = {k_t(n)} / {\\tbinom{n}{t}} and c_t be the limit of c_t(n) for n going to infinity. A 1962 conjecture of Erdos stating that c_t = 2^{1-\\tbinom{t}{2}} was disproved by Thomason in 1989 for all t &gt; 3. Tighter counterexamples have been constructed by Jagger, Stovicek and Thomason in 1996, by Thomason for t &lt; 7 in 1997, and by Franek for t=6 in 2002. We present a computational framework to investigate tighter upper bounds for small t yielding the following improved upper bounds for t=6,7 and 8: c_6 \\leq 0.7445 \\times 2^{1- \\tbinom{6}{2}}, c_7\\leq 0.6869\\times 2^{1- \\tbinom{7}{2}}, and c_8 \\leq 0.7002\\times 2^{1- \\tbinom{8}{2}}. The constructions are based on a large but highly regular variant of Cayley graphs for which the number of cliques and cocliques can be expressed in closed form. Considering the quantity e_t=2^{\\tbinom{t}{2}-1} c_t, the new upper bound of 0.687 for e_7 is the first bound for any e_t smaller than the lower bound of 0.695 for e_4 due to Giraud in 1979.&lt;br /&gt;The second part of the thesis deals with extremal periodicities in strings: we consider the problem of the maximum number of distinct squares in a string. The importance of considering as key variables both the length n and the size d of the alphabet is stressed. Let (d,n)-string denote a string of length n with exactly d distinct symbols. We investigate the function \\sigma_d(n) = max {s(x) | x} where s(x) denotes the number of distinct primitively rooted squares in a (d,n)-string x. We discuss a computational framework for computing \\sigma_d(n) based on the notion of density and exploiting the tightness of the available lower bound. The obtained computational results substantiate the hypothesized upper bound of n-d for \\sigma_d(n). The structural similarities with the approach used for investigating the Hirsch bound for the diameter of a polytope of dimension d having n facets is underlined. For example, the role played by (d,2d)-polytope was presented in 1967 by Klee and Walkup who showed the equivalency between the Hirsch conjecture and the d-step conjecture.&lt;/p&gt;","abstract_has_math":false,"creators":["LIU, MIN JING"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computing and Software","school":null,"contributors":[],"advisors":["Deza, Antoine","Franek, Frantisek","Alexander Rosa, Ryszard Janicki, Dalibor Froncek"],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-10","date_published":"2013-10","updated_at":"2026-11-18T19:37:13Z","subjects":["Combinatorial optimization","Discrete Mathematics","Graph theory","Combinatorial framework","String","Heuristics","Discrete Mathematics and Combinatorics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/18072"],"render_values":[{"text":"https://doi.org/10.71548/18072","href":"https://doi.org/10.71548/18072","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/8369","9456","4631116"],"render_values":[{"text":"opendissertations/8369","href":null,"code":true},{"text":"9456","href":null,"code":true},{"text":"4631116","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/13533","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/13533","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F13533","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Deza, Antoine","Franek, Frantisek","Alexander Rosa, Ryszard Janicki, Dalibor Froncek"]},{"key":"dc:contributor.department","label":"Department","values":["Computing and Software"]},{"key":"dc:creator","label":"Author","values":["LIU, MIN JING"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-06-18T17:04:20Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-06-18T17:04:20Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2013-09-25"]},{"key":"dc:date.issued","label":"Date","values":["2013-10"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorial optimization","Discrete Mathematics","Graph theory","Combinatorial framework","String","Heuristics","Discrete Mathematics and Combinatorics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/8369","9456","4631116"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/13533","https://doi.org/10.71548/18072"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["<p>As stressed by the Society for Industrial and Applied Mathematics (SIAM): Applied mathematics, in partnership with computational science, is essential in solving many real-world problems. Combinatorial optimization focuses on problems arising from discrete structures such as graphs and polyhedra. This thesis deals with extremal graphs and strings and focuses on two problems: the Erdos' problem on multiplicities of complete subgraphs and the maximum number of distinct squares in a string.<br />The first part of the thesis deals with strengthening the bounds for the minimum proportion of monochromatic t cliques and t cocliques for all 2-colourings of the edges of the complete graph on n vertices. Denote by k_t(G) the number of cliques of order t in a graph G. Let k_t(n) = min{k_t(G)+k_t(\\overline{G})} where \\overline{G} denotes the complement of G of order n. Let c_t(n) = {k_t(n)} / {\\tbinom{n}{t}} and c_t be the limit of c_t(n) for n going to infinity. A 1962 conjecture of Erdos stating that c_t = 2^{1-\\tbinom{t}{2}} was disproved by Thomason in 1989 for all t > 3. Tighter counterexamples have been constructed by Jagger, Stovicek and Thomason in 1996, by Thomason for t < 7 in 1997, and by Franek for t=6 in 2002. We present a computational framework to investigate tighter upper bounds for small t yielding the following improved upper bounds for t=6,7 and 8: c_6 \\leq 0.7445 \\times 2^{1- \\tbinom{6}{2}}, c_7\\leq 0.6869\\times 2^{1- \\tbinom{7}{2}}, and c_8 \\leq 0.7002\\times 2^{1- \\tbinom{8}{2}}. The constructions are based on a large but highly regular variant of Cayley graphs for which the number of cliques and cocliques can be expressed in closed form. Considering the quantity e_t=2^{\\tbinom{t}{2}-1} c_t, the new upper bound of 0.687 for e_7 is the first bound for any e_t smaller than the lower bound of 0.695 for e_4 due to Giraud in 1979.<br />The second part of the thesis deals with extremal periodicities in strings: we consider the problem of the maximum number of distinct squares in a string. The importance of considering as key variables both the length n and the size d of the alphabet is stressed. Let (d,n)-string denote a string of length n with exactly d distinct symbols. We investigate the function \\sigma_d(n) = max {s(x) | x} where s(x) denotes the number of distinct primitively rooted squares in a (d,n)-string x. We discuss a computational framework for computing \\sigma_d(n) based on the notion of density and exploiting the tightness of the available lower bound. The obtained computational results substantiate the hypothesized upper bound of n-d for \\sigma_d(n). The structural similarities with the approach used for investigating the Hirsch bound for the diameter of a polytope of dimension d having n facets is underlined. For example, the role played by (d,2d)-polytope was presented in 1967 by Klee and Walkup who showed the equivalency between the Hirsch conjecture and the d-step conjecture.</p>"]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Doctor of Philosophy (PhD)"]},{"key":"dc:title","label":"Title","values":["COMBINATORIAL OPTIMIZATION APPROACHES TO DISCRETE PROBLEMS"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Deza, Antoine","Franek, Frantisek","Alexander Rosa, Ryszard Janicki, Dalibor Froncek"],"dc:contributor.department":["Computing and Software"],"dc:creator":["LIU, MIN JING"],"dc:date.accessioned":["2014-06-18T17:04:20Z"],"dc:date.available":["2014-06-18T17:04:20Z"],"dc:date.created":["2013-09-25"],"dc:date.issued":["2013-10"],"dc:description.abstract":["<p>As stressed by the Society for Industrial and Applied Mathematics (SIAM): Applied mathematics, in partnership with computational science, is essential in solving many real-world problems. Combinatorial optimization focuses on problems arising from discrete structures such as graphs and polyhedra. This thesis deals with extremal graphs and strings and focuses on two problems: the Erdos' problem on multiplicities of complete subgraphs and the maximum number of distinct squares in a string.<br />The first part of the thesis deals with strengthening the bounds for the minimum proportion of monochromatic t cliques and t cocliques for all 2-colourings of the edges of the complete graph on n vertices. Denote by k_t(G) the number of cliques of order t in a graph G. Let k_t(n) = min{k_t(G)+k_t(\\overline{G})} where \\overline{G} denotes the complement of G of order n. Let c_t(n) = {k_t(n)} / {\\tbinom{n}{t}} and c_t be the limit of c_t(n) for n going to infinity. A 1962 conjecture of Erdos stating that c_t = 2^{1-\\tbinom{t}{2}} was disproved by Thomason in 1989 for all t > 3. Tighter counterexamples have been constructed by Jagger, Stovicek and Thomason in 1996, by Thomason for t < 7 in 1997, and by Franek for t=6 in 2002. We present a computational framework to investigate tighter upper bounds for small t yielding the following improved upper bounds for t=6,7 and 8: c_6 \\leq 0.7445 \\times 2^{1- \\tbinom{6}{2}}, c_7\\leq 0.6869\\times 2^{1- \\tbinom{7}{2}}, and c_8 \\leq 0.7002\\times 2^{1- \\tbinom{8}{2}}. The constructions are based on a large but highly regular variant of Cayley graphs for which the number of cliques and cocliques can be expressed in closed form. Considering the quantity e_t=2^{\\tbinom{t}{2}-1} c_t, the new upper bound of 0.687 for e_7 is the first bound for any e_t smaller than the lower bound of 0.695 for e_4 due to Giraud in 1979.<br />The second part of the thesis deals with extremal periodicities in strings: we consider the problem of the maximum number of distinct squares in a string. The importance of considering as key variables both the length n and the size d of the alphabet is stressed. Let (d,n)-string denote a string of length n with exactly d distinct symbols. We investigate the function \\sigma_d(n) = max {s(x) | x} where s(x) denotes the number of distinct primitively rooted squares in a (d,n)-string x. We discuss a computational framework for computing \\sigma_d(n) based on the notion of density and exploiting the tightness of the available lower bound. The obtained computational results substantiate the hypothesized upper bound of n-d for \\sigma_d(n). The structural similarities with the approach used for investigating the Hirsch bound for the diameter of a polytope of dimension d having n facets is underlined. For example, the role played by (d,2d)-polytope was presented in 1967 by Klee and Walkup who showed the equivalency between the Hirsch conjecture and the d-step conjecture.</p>"],"dc:description.degree":["Doctor of Philosophy (PhD)"],"dc:identifier.other":["opendissertations/8369","9456","4631116"],"dc:identifier.uri":["http://hdl.handle.net/11375/13533","https://doi.org/10.71548/18072"],"dc:subject":["Combinatorial optimization","Discrete Mathematics","Graph theory","Combinatorial framework","String","Heuristics","Discrete Mathematics and Combinatorics"],"dc:title":["COMBINATORIAL OPTIMIZATION APPROACHES TO DISCRETE PROBLEMS"],"dc:type":["thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:37:13Z"}