An apple A_{k} is a graph obtained from a chordless cycle C_{k} of length k ≥ 4 by adding a vertex that has exactly one neighbor on the cycle. A graph is *apple-free* if it contains no A_{k}, k ≥ 4, as an induced subgraph. Since every apple contains an induced claw, a chordless cycle of length at least four, and an induced path on four vertices, the class of apple-free graphs generalizes that of claw-free graphs, chordal graphs, and cographs. In this work, we provide an explicit description of the structure of all apple-free graphs.

Nonnegativity of a polynomial does not generally imply that it can be written as a sum of squares of polynomials, except in a few cases, such as the polynomial being separable or it being quadratic. Here we study polynomials that are sums of separable and quadratic terms. We show that being nonnegative and being sum of squares are not equivalent for polynomials of this structure. In fact, we show that the equivalence only holds true for the same cases as those for which nonnegative polynomials are sum of squares. We then show that deciding nonnegativity of polynomials of this structure is NP-hard, whereas deciding convexity amounts to solving a single semidefinite program. We also show that convex polynomials of this structure are nonnegative if and only if they are sum of squares, a property that is not true for general convex polynomials. Finally, we present possible application areas where sums of separable and quadratic polynomials appear and perform some numerical experiments.

%G eng %0 Journal Article %D In Preparation %T A sum of squares characterization of perfect graphs. %A Amir Ali Ahmadi %A Cemil Dibek %X In this work, we introduce and study the notion of sos-perfectness. For a graph G, we define a certain quartic homogeneous polynomial p_{G}(x) based on the adjacency relation in G and show that p_{G}(x) is nonnegative for every graph G. A graph G is *perfect* if for every induced subgraph H of G, the chromatic number of H equals the clique number of H. A graph G is *sos-perfect* if p_{H}(x) is sum of squares (sos) for every induced subgraph H of G. We show that a graph is perfect if and only if it is sos-perfect. This equivalence together with the strong perfect graph theorem allows us to explicitly provide an infinite family of nonnegative polynomials that are not sos.

We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.

%G eng %U https://arxiv.org/abs/2005.05042 %0 Journal Article %D Submitted %T Evolution of Q Values for Deep Q Learning in Stable Baselines %A Matthew Andrews %A Cemil Dibek %A Karina Palyutina %X We investigate the evolution of the Q values for the implementation of Deep Q Learning (DQL) in the Stable Baselines library. Stable Baselines incorporates the latest Reinforcement Learning techniques and achieves superhuman performance in many game environments. However, for some simple non-game environments, the DQL in Stable Baselines can struggle to find the correct actions. In this paper we aim to understand the types of environment where this suboptimal behavior can happen, and also investigate the corresponding evolution of the Q values for individual states. We compare a smart TrafficLight environment (where performance is poor) with the AI Gym FrozenLake environment (where performance is perfect). We observe that DQL struggles with TrafficLight because actions are reversible and hence the Q values in a given state are closer than in FrozenLake. We then investigate the evolution of the Q values using a recent decomposition technique of Achiam et al.. We observe that for TrafficLight, the function approximation error and the complex relationships between the states lead to a situation where some Q values meander far from optimal. %G eng %U https://arxiv.org/abs/2004.11766 %0 Journal Article %D Submitted %T New examples of minimal non-strongly-perfect graphs. %A Maria Chudnovsky %A Cemil Dibek %A Paul Seymour %X A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs. %G eng %U https://arxiv.org/abs/2003.01846 %0 Journal Article %J to appear in Journal of Graph Theory %D 2020 %T Strongly perfect claw-free graphs - a short proof. %A Maria Chudnovsky %A Cemil Dibek %X A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization. %B to appear in Journal of Graph Theory %G eng %U https://arxiv.org/abs/1912.05645 %0 Journal Article %J Discrete Mathematics %D 2017 %T Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded. %A C. Dibek %A T. Ekim %A P. Heggernes %X We determine the maximum number of edges that a claw-free graph can have, when its maximum degree and matching number are bounded. This is a famous problem that has been studied on general graphs, and for which there is a tight bound. The graphs achieving this bound contain in most cases an induced copy of K